数据结构试卷(一)
三、计算题(每题 6分，共24 分)
1.
针为
2.
在如下数组A中存储了一个线性表，表头指A [0].next ，试写出该线性表。
请画出下图的邻接矩阵和邻接表。
data n ext
3 4 5 60 6 7
50 7 78 2 90 0 34 40 1 3 5 4 3.
已知一个图的顶点集 V和边集E分别为：V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
4. 画出向小根堆中加入数据 4, 2, 5, 8, 3 时，每加入一个数据后堆的变化。 四、 阅读算法(每题 7分，共14分)
1. LinkList mynote(LinkList L)
{//L
是不带头结点的单链表的头指针
if(L&&L-> next){
q=L
51 52
}
: :
； L=L— >next ; p=L;
while(p — >next) p=p — >next ; p — >next=q ; q — >next=NULL;
return L }
;
请回答下列问题：
(1 )说明语句S1的功能； (2) 说明语句组S2的功能；
(3) 设链表表示的线性表为(a1,a 2,…,an),写出算法执行后的返回值所表示的线 性表。
2. void ABC(BTNode * BT)
{ if BT {
ABC (BT->left); ABC (BT->right); cout<
该算法的功能是：
五、 算法填空(共 8分)
二叉搜索树的查找一一递归算法
{
：
bool Find(BTreeNode* BST,ElemType& item)
if (BST==NULL) return false; //
查找失败
else {
if (item==BST->data){
item=BST->data;// 查找成功 return else if(item
return Find( _____________________ ,item); else return Find( _____________________ ,item); }//if
}
;}
六、编写算法(共 8 分) 统计出单链表 HL 中结点的值等于给定值 X 的结点数。 int CountX(LNode*
HL,ElemType x)
数据结构试卷(二)
三、应用题(36分)
1.
设一组初始记录关键字序列为
4趟直接插入排序后的结果。
(45 , 80, 48, 40, 22, 78)，则分别给出第4趟简单选择 排序和第
2.
设指针变量p指向双向链表中结点 A,指针变量q指向被插
的后面插入结点 B的操作序列(设双向链表中结点的两个指针域分别为
llink和rlink )。
入结点 B,要求给出在结点 A
3.
62, 83, 90)，查找方法用
设一组有序的记录关键字序列为 (13 , 18, 24, 35, 47, 50,
二分查找，要求计算出查找关键字 度。
62时的比较次数并计算出查找成功时的平均查找长
4.
设一棵树 T 中边的集合为｛(A , B), (A , C), (A , D), (B, E) , (C , F) , (C , G)｝，要求 用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。 设有无向图G,要求给出用普里姆算法构造最小生成树所走过的边的集合。
5.
6.
设有一组初始记录关键字为 (45 , 80 , 48 , 40 , 22 , 78),要求构
造一棵二叉排序树并给
出构造过程。 四、算法设计题(16分)
1.
设有一组初
O(n)的时间
K,右半部分的每个
始记录关键字序列(K1 , K2 ,…,K0,要求设计一个算法能够在
复杂度将线性表划分成两部分，其中左半部分的每个关键字均小于 关键字均大于等于 K。
2.
设有两个集合 A和集合B,要求设计生成集合 C=AH B的算法，其中集合 A B和C用链 式存储结构表示。
数据结构试卷(三)
?填空题
1.
下列算法实现在顺序散列表中查找值为
x的关键字，请在下划线处填上正确的语句。
struct record{i nt key; int others;};
int hashsqsearch(struct record hashtable[ ],i nt k) {
int i,j; j=i=k % p; while
(hashtable[j].key!=k&&hashtable[j].flag!=0){j=( ________ )
%m; if (i==j)
return(-1);}
if ( _____________________________ ) return(j); else return(-1); } 2.
下列算法实现在二叉排序树上查找关键值
k,请在下划线处填上正确的语句。
typedef struct
node{int key; struct node *lchild; struct node *rchild;}bitree;
bitree *bstsearch(bitree *t, int k) {
if (t==0 ) return(0);else while (t!=0)
if (t->key==k) ________________________ ; else if (t->key>k) t=t->lchild;
else _________________ ; }
三、计算题(每题10分，共30分)
1.
已知二叉树的前序遍历序列是 AEFBGCDHIKJ中序遍历序列是 EFAGBCHKIJ，画出此二叉
树，并画出它的后序线索二叉树。
2.
已知待散列的线性表为(36，15，40，63, 22)，散列用的一维地址空间为[0 .. 假定 选用的散列函数是 H( K) = K mod 7，若发生冲突采用线性探查法处理，试： (1 )计算出每一个元素的散列地址并在下图中填写出散列表：
'
0
1 2
3 4
5 6
(2)求出在查找每一个元素概率相等情况下的平均查找长度。
3.
已知序列(10，18，4，3，6，12，1，9，18，8)请用快速排序写出每一趟排序的结果。 四、算法设计题(每题15分，共30分)
1. 设计在单链表中删除值相同的多余结点的算法。 2.
设计一个求结点x在二叉树中的双亲结点算法。
6]，
数据结构试卷(四)
1.
20为中轴的一趟快速
设一组初始记录关键字序列为 (20, 18, 22, 16, 30, 19)，则以
排序结果为 __________________________________ 。
2.
设一组初始记录关键字序列为 (20，18, 22，16, 30，19)，则根
建成的初始堆为 ____________________________ 。
据这些初始关键字序列
设某无向图G中有n个顶点，用邻接矩阵
i和顶点j
A作为
3.
该图的存储结构，则顶点
互为邻接点的条件是 __________________________ 。
4.
设无向图对应的邻接矩阵为 __________________ A,则A中第i上第i列上非0
非0元素的个数
元素的个数(填等于，大于或小于)。
5.
BADC则后序遍历该
设前序遍历某二叉树的序列为 ABCD中序遍历该二叉树的序列为
二叉树的序列为 ______________ 。
6.
设散列函数H(k)=kmodp，解决冲突的方法为链地址法。要求在下列算法划线处填上 正确的语句完成在散列表
hashtalbe中查找关键字值等于
0。
k的结点，成功时返回指向关
键字的指针，不成功时返回标志
typedef struct node {int key; struct node *n ext;} lklist; void createlkhash(lklist *hashtable[]) {
int i,k; lklist *s;
for(i=0;i s=(lklist *)malloc(sizeof(lklist)); s_>key=a[i]; k=a[i] % p; s->next=hashtable[k]; ; } } 三、计算题(每题10分，共30分) 1、 画出广义表 LS=(( ) , (e) , (a , (b , c , d ))) 2、 下图所示的森林： 的头尾链表存储结构。 (1) 求树(a)的先根序列和后根序列； (2) 求森林先序序列和中序序列； (3) 将此森林转换为相应的二叉树； 3、设散列表的地址围是[0..9 ]，散列函数为 H( key) = (key 2 +2) MOD 9,并采用链表 处理冲突，请画出 元素 1 7、4、5、3、6、2、8、9依次插入散列表的存储结构。 四、算法设计题(每题10分，共30分) .设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表 中结点空间
东南大学十套数据结构试题与答案
