数据结构试题及答案(10套最新) 下载本文

第一部分 选择题(30分)

一、项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个选项中只有一个选项是符合题目要求的,请将正确选项前的字母填在题后的括号内。

1.算法指的是( )

A.计算机程序 B.解决问题的计算方法

C.排序算法 D.解决问题的有限运算序列 2.线性表采用链式存储时,结点的存储地址( ) A.必须是不连续的 B.连续与否均可 C.必须是连续的

D.和头结点的存储地址相连续

3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为( )

A.O(1) B.O(n) C.O(m) D.O(m+n) 4.由两个栈共享一个向量空间的好处是:( ) A.减少存取时间,降低下溢发生的机率 B.节省存储空间,降低上溢发生的机率

C.减少存取时间,降低上溢发生的机率 D.节省存储空间,降低下溢发生的机率

5.设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为( )

A.front=front+1 B.front=(front+1)%(m-1) C.front=(front-1)%m D.front=(front+1)%m 6.如下陈述中正确的是( )

A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中元素只能是字母 D.空串就是空白串

7.若目标串的长度为n,模式串的长度为[n/3],则执行模式匹配算法时,在最

n坏情况下的时间复杂度是( )

A.O(3) B.O(n) C.O(n2) D.O(n3) 8.一个非空广义表的表头( )

A.不可能是子表 B.只能是子表

C.只能是原子 D.可以是子表或原子 9.假设以带行表的三元组表表示稀疏矩阵,则和下列行表

0 2 3 3 5 ?0?806??0?7000??0?70?806??????0 对应的稀疏矩阵是( ) ??00000?5A.?0B.00?????0704D.? 052000?C.???0?0000????5040?? ? ??5???? ?0000? ?0?8?8000003006?6?000???400?0??000?0??040??0 ?300??

10.在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为

0的结点个数为( )

A.4 B.5 C.6 D.7

11.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A.e B.2e C.n2-e D.n2-2e

12.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi

相关的所有弧的时间复杂度是( ) A.O(n) B.O(e) C.O(n+e) D.O(n*e)

13.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进

行排序时,序列的变化情况如下: 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84 则所采用的排序方法是( )

A.选择排序 B.希尔排序 C.归并排序 D.快速排序 14.适于对动态查找表进行高效率查找的组织结构是( )

A.有序表 B.分块有序表 C.三叉排序树 D.线性链表 15.不定长文件是指( )

A.文件的长度不固定 B.记录的长度不固定 C.字段的长度不固定 D.关键字项的长度不固定

第二部分 非选择题(共70分)

二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,

共20分)不写解答过程,将正确的答案写在每小题的空格内。错填或不填均无分。

16.数据的逻辑结构是从逻辑关系上描述数据,它与数据的 无关,是独立于计算机的。

17.在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head= 。 18.栈顶的位置是随着 操作而变化的。

19.在串S=“structure”中,以t为首字符的子串有 个。

20.假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中,其

中B[0]存储矩阵中第1个元素a1,1,则B[31]中存放的元素是 。 21.已知一棵完全二叉树中共有768结点,则该树中共有 个叶子结点。

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.下列算法的功能是比较两个链串的大小,其返回值为:

??1当s1?s2??0当s1?s2?1当s?s12 comstr(s1,s2)=?请在空白处填入适当的内容。

int comstr(LinkString s1,LinkString s2) {//s1和s2为两个链串的头指针 while(s1&&s2){

if(s1->datedate)return-1; if(s1->date>s2->date)return1; ① ; ② ; }

if( ③ )return-1; if( ④ )return1; ⑤ ; }

① ② ③ ④ ⑤

31.阅读下面的算法

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针 if(L&&L->next){

q=L;L=L->next;p=L; S1: while(p->next) p=p->next; S2: p->next=q;q->next=NULL; }

return L; }

请回答下列问题:

(1)说明语句S1的功能; (2)说明语句组S2的功能;

(3)设链表表示的线性表为(a1,a2, ?,an),写出算法执行后的返回值所表示的线性表。

32.假设两个队列共享一个循环向量空间(参见右

下图),

其类型Queue2定义如下: typedef struct{