首页 > 学生作文 > 读后感 > 读后感800字 >

数据结构试题及答案（10套）

由天下分享时间：2025/3/3 22:06:05 加入收藏我要投稿点赞

22．已知一个图的广度优先生成树如右图所示，则与此相

应的广度优先遍历序列为。

23．在单链表上难以实现的排序方法有和。 24．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进

行的关键字比较次数为。 25．多重表文件和倒排文件都归属于文件。三、解答题（本大题共4小题，每小题5分，共20分） 26．画出下列广义表的共享结构图形表示

P=（（（z）,(x,y)）,((x,y),x),(z)） 27．请画出与下列二叉树对应的森林。

?01001?

?10010??? ?00011???28．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示 ?01101??10110?? a ?b (1)画出该图的图形；

c （2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，d 写出相应的遍历序列。 e

29．已知一个散列表如下图所示： 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12

其散列函数为h(key)=key, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+i*h1(key))%m i=0,1,…，m－1 其中

h1(key)=key+1 回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少

（2）该散列表在等概率查找时查找成功的平均查找长度为多少四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．下列算法的功能是比较两个链串的大小，其返回值为：

comstr(s1,s2)=

??1当s1?s2??0当s1?s2?1当s?s12?

请在空白处填入适当的内容。

int comstr(LinkString s1,LinkString s2)

{关键字

三、解答题（本大题共4小题，每小题5分，共20分） 26．

图1 图2 27．

深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１； 3?2?1?1?29ASL??55 （２）平均查找长度

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30． ①S1=S1－>next ②s2=s2－>next

③s2(或s2!=NULL或s2&&!s1) ④s1(或s1!=NULL或s1&&!s2) ⑤return 0

31.（1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,an,a1）

28．该图的图形为：

32. ①(i＋1)%2(或1－i) ②Q－>rear[i]

③(Q－>rear[i]＋)%Maxsize 33.(1)Leafhead

F H G D ∧ （2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以

Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。

五、算法设计题（本题共10分） 34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。（2）int f(int b[],int n) 或 int f(int b[],int n) { {

int p,q； int p,q；

p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； return q－p； return p－q； } }

一、选择题（20分）

1．组成数据的基本单位是（）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。 (A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合 3．数组的逻辑结构不同于下列（）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（）个。 (A) 2i (B) 2i (C) 2i-1 (D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。

(A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。 (A) 6 (B) 4 (C) 3 (D) 2

7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。 (A) 100 (B) 40 (C) 55 (D) 80

8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。 (A) 3 (B) 4 (C) 5 (D) 1

9．根据二叉树的定义可知二叉树共有（）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10. 设有以下四种排序方法，则（）的空间复杂度最大。 (A) 冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希尔排序

二、填空题(30分)

1. 设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。

3. 设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。

4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。

5. 设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。

6. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。

7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。

8. 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。

9. 下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。

int index(char s[ ], char t[ ]) {

i=j=0;

while(i

if (j==strlen(t))return(i-strlen(t));else return (-1); }

10. 设一个连通图G中有n个顶点e条边，则其最小生成树上有________条边。