数据结构练习题

《数据结构》模拟测试题

一、 选择题（共30分，每小题2分）

1.在一个长度为n的顺序表的第i（0<=i

A．n-i B.n-i+1 C.n-i-1 D.i 2．设有一个无向图G=(V，E)和G＇=(V＇，E＇)，如果G＇是G的生成树，则下面不正确的说法是＿＿＿＿。

a.G＇为G的子图 b.G＇为G的连通分量 c.G＇为G的极小连通子图且V＇=V d.G＇是G的一个无环子图 3.带头结点head的单链表L为空的判断条件是（ ）

A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL 4.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除表中的第一个元素，则采用（ ）存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双向链表 D.仅有尾指针的单循环链表

5.设有一个顺序栈S，元素a b c d e f依次进栈，如果6个元素出栈的顺序是b d c f e a，则栈的容量至少应该是（ ）

A.2 B.3 C.5 D.6

6．向一个栈顶指针为top的带头结点的链栈中插入一个s所指结点，则其操作步骤是（ ）

A.top->next=s; B.s->next=top->next;top->next=s; C.s->next=top;top=s; D. s->next=top;top= top->next;

7. 以下为单链表的查找算法, 假设表长为N，则算法的时间复杂度为（ ）

A）O（1） B） O（N） C） O（N*N） D） O（NlogN）

NODE *get(NODE *head,intｉ） ｛ NODE *p; int counter = 0; p=head->next; while((p!=NULL)&&(counternext; counter++; } if((p!=NULL)&&(counter == i)) return p; else return NULL; } 8. 设以数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为＿＿＿＿。

a.front:=front+1 b.front:=(front+1) % m c.rear:=(rear+1) % m d.front:=(front+1) % (m+1) 9. 深度为6（根的层次为１）的二叉树至多有＿＿＿＿结点。

a.31 b.32 c.63 d.64

10.一棵非空的二叉树的前序遍历序列和后序遍历序列正好相同，则该二叉树一定满足（ ）

A.所有的结点均无左孩子 B.所有的结点均无右孩子 C.只有一个孤立的结点 D.是任意一棵二叉树

11. 已知字符A、B、C、D的使用频率（权值）分别为7，9，27，22。对其进行HUFFMAN编码，各字符对应的编码为（ ）

A） A（0001）B（100）C（110） D（0） B） A（100）B（101）C（0） D（11） C） A（100）B（1001）C（11） D（1） D） A（101）B（100）C（0） D（00）

12.在N条边的无向图的邻接表存储中，边表中结点的总数为（ ） A.N B.2N C.N/2 D.N-1 13.与其他查找方法相比，散列查找的特点是（ ）。 A.通过关键字的比较进行查找

B.通过关键字计算元素的存储地址进行查找

C.通过关键字计算元素的存储地址并进行一定的比较进行查找 D.以上都不是

14.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最后选用（ ）排序法。

A.冒泡排序 B.快速排序 C.堆排序 D.直接插入排序 15.对序列（15，9，7，8，20，-1，4）进行排序，进行一趟排序后，数据的排列变为（4，9，7，8，-1，15，20），则采用的是（ ）排序。 A.选择排序 B.快速排序 C.希尔排序 D.冒泡排序 二、填空题（20分，每空2分）

16.栈的逻辑特点是___________，队列的逻辑特点是＿先进先出_________。 17、深度为K的完全二叉树至少有______个结点，至多有____个结点。 18、设F是由T1，T2,T3三棵树组成的森林，与F对应的二叉树为B。已知T1,T2,T3的结点数分别为x，y，z，则该二叉树B的左子树中有_____个结点，右子树中有_____个结点。

19、 栈下溢是指在____________时进行出栈操作。栈上溢是指在____________时进行进栈操作

20. 在有向图中，以顶点v为终点的边的数目称为v的____________。 21.常用的数据结构有：集合、线性结构、树型结构和_________。 三、应用题（共25分）

22．已知，一棵二叉树中根遍历的结点序列为DCBGEAHFIJK，先根遍历的结点序列为ABCDEGFHJIK，画出对应的二叉树。（5分）

23. 下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权值表示修建公路所需的代价。请画出其邻接表，并选择能够沟通每个城市且总造价最省的n-1条公路。画出所有可能的方案（5分）（见图1） 。

图1

24.设给定的排序码序列为（72，73，71，23，94，16，05，68），请写出归并排序过程中每趟排序的结果。（5分）

25.假定一个待存储的线性表为（32，75，29，94，16，05，68，63，48，94，25，36，18，70），散列地址空间为HT[17]，散列函数为H（k）=key,若采用线性探查法处理冲突，请计算每个元素的散列地址。画出最后得到的散列表，并求出平均查找长度。（10分） 四、分析给定的代码，写出所完成的功能。（１２分）

26. 代码如下：（５分）

bitree * CREAT_AAA ( ) { bitree *t； datatype x;

printf(\请输入正整数以0作为结束标志: \ scanf(\ /* 输入结点的数据值 */ if (x==0) t=NULL; /* 输入数据，以0结束 */ else

{ t=(struct node*)malloc(sizeof(bitree)); /* 生成新结点 */ t->data=x; /* 输入新结点的数据值 */ t->lchild= CREAT_AAA (); ／* */ t->rchild= CREAT_AAA (); ／* */ }

return(t); /* 返回树的根结点 */ }/* CREAT_AAA */

27.代码如下：（７分）

LinkList A2(LinkList A,LinkList B) { LinkList C; LNode *p,*q,*s; p=A->next; q=B->next; C=A; delete B; while(p&&q) { if(p->datadata) {s=p;p=p->next;} else {s=q;q=q->next;} s->next=C->next; C->next=s; }

if(p==NULL) p=q; while(p) { s=p; p=p->next; s->next=C->next; C->next=s; } }

五、编写算法（1３分）

28、编写单链表的逆置算法。（７） 单链表结点存储结构定义为： typedef struct Node {

int data;

struct Node *next; }LNode,*LinkList;

29．设一棵二叉树以二叉链表为存储结构，结点包含lchild、data和rchild三个字段。设计算法，求出在先序序列中处于第k个位置的结点。 (６分)

lchild data rchild 函数形式： int findNODE(bitree *root, int k)

本文来源：https://www.bwwdw.com/article/don3.html