文档库

最新最全的文档下载
当前位置:文档库 > 数据结构期末考试题26

数据结构期末考试题26

一、判断:(共10分,每题1分,)

数据结构期末考试题26

( )

F 指向队列的头结点,尾指针R 指向队列的尾结点。( ) ( )

( ) 5.稀疏矩阵中0元素的分布有规律,因此可以采用三元组方法进行压缩存储。

数据结构期末考试题26

( )

6.若线性表采用顺序存储结构,每个数据元素占用4个存储单元,第12个数据元素的存储

地址为144,则第1个数据元素的存储地址是101。( )

7.如果一个串中的所有字符均在另一串中出现,则说前者一定是后者的子串。( )

8.数组是向量推广。( )

数据结构期末考试题26

9.将一棵树转换成二叉树后,根结点没有左子树;( ) 10.哈希表的查找无需进行关键字的比较。( )

二、填空:(共20分,每空2分,)

1.线性表可以在 _______位置进行插入,栈可以在_____位置进行插入,队列可以在_____位置进行插入。

2.在非空线性表中除第一个元素外,集合中每个数据元素只有一个_________;除最后一个元素之外,集合中每个数据元素均只有一个__________。

3.在栈的顺序实现中,栈顶指针top ,栈为空条件______________。

4.某带头结点的单链表的头指针head ,判定该单链表非空的条件________________。

5. 在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24,需要进行

______________次元素之间的比较。

6.对关键字序列(50,34,92,19,11,68,56,41,79)进行直接插入排序,当将第7个关

键字56插入到当前的有序子表中,为寻找插入位置需进行________次比较。

7.如果从一个顶点出发又回到该顶点,则此路径叫做_______。

三、选择题:(共20分,每题2分)

1. 二维数组A 按行顺序存储,其中每个元素占1个存储单元。若A[1][1]的存储地址为420,

A[3][3]的存储地址为446,则A[5][5]的存储地址为_______ A.470

B.471

C.472

D.473

2.线性表若采用链表存储结构时,要求内存中可用存储单元的地址_________

A.必须是连续的

B.部分地址必须是连续的

C.一定是不连续的

D.连续不连续都可以 3.下面程序段的时间复杂度为____________ for(int i=0; i

A.O(m 2)

B.O(n 2

) C.O(m*n) D.O(m+n) 4.队和栈的主要区别是___________

A.逻辑结构不同

B.存储结构不同

C.所包含的运算个数不同

D.限定插入和删除的位置不同 5.一个非空广义表的表头_________

A.不可能是子表

B.只能是子表

C.只能是原子

D.可以是子表或原子

6.假定一个顺序队列的队首和队尾指针分别为front 和rear ,存放该队列的数 组长度为N ,则判断队空的条件为________ A.(front+1)% N == rear B .(rear+1)% N == front C . front == rear D . front == 0

7.在一个单链表HL 中,若要向表头后插入一个由指针p 指向的结点,则执行 ________ A.HL = p;p->next = HL; B.p->next = HL;HL = p;

C.p->next = HL;p = HL;

D.p->next = HL->next;HL->next = p;

8.在目标串T[0…n-1]=‘xwxxyxy ’中,对模式串p[0…m-1]=‘xy ’进行子串定位操作的 结果___________

A.0

B.2

C.3

D.5 9.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵,则此图是_______

A.有向完全图

B.连通图

C.强连通图

D.有向无环图 10.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为________。 A 、 24 B 、 48

C 、 72

D 、 53

专业: 姓

四、应用题(30分):

1.已知稀疏矩阵如下:请写出该稀疏矩阵三元组表示。(6分)

数据结构期末考试题26

2.序列(46,88,45,39,70,58,101,10,66,34)建立一个二叉排序树,画出该二叉树,并求在等概率情况下查找成功的平均查找长度。(6分)

3、考虑下图:

(1)顶点A出发,求它的深度优先生成树。

(2)从顶点A出发,求它的广度优先生成树。

(3)根据普里姆算法,求它的最小生成树。(共12分)

数据结构期末考试题26

4. 设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该二叉树。(6分)

五.程序题(20分)

1、算法填空:(每空2分,共8分)

完成二叉树按层遍历的算法。

Void leveltravel ( struct treenode *bt)

{ struct treenode *p,*a[n];

int rear=front = -1;

p=bt;

rear =__________;

a[rear]=p;

while (rear != front)

{ front = ___________;

p=a[front];

printf(“%c”,p->data);

数据结构期末考试题26

数据结构期末考试题26

If ( p->left !=null)

{ rear =(rear +1)% n

a[rear]= _________; }

If (p->right!= null)

{rear = (rear +1)%n ;

a[rear]=_________; }

}

}

2、阅读下列算法,并回答下列问题:(8分)

完善程序,并回答该算法完成什么功能?算法中r[n+1]的作用是什么?void sort (elemtype r[],int n)

{int k,i;

for(k=n-1;k>=1;k- -)

if(r[k]>r[k+1])

{ r[n+1]=r[k];

for(i=k+1;r[i]

r[i-1]=r[i];

;}

}}

3.说出下面算法完成的功能。(4分)

void delete( int a[n],int i)

{if (i<0)||(i>=n) printf(“error”);

else

{for (j=i-1;j

a[j]=a[j+1];

n=n-1;}

}