天津科技大学数据结构 试卷八.doc

《数据结构》试卷八

一、填空题:(共20分)
1、线性结构是数据元素的非空有限集,存在唯一的最后一个元素,除该元素外,其余元素有直接后继.
2、Head[Tail[(b,k,m,g)]]= .
3、对n阶对称矩阵进行压缩存储,一般只存储中元素,此时只需个元素的存储空间.
.
5、若P指向单链表的尾结点时,则有P^.NEXT= 。
6、如图: a 该树中叶子结点,分支结点, 该树度分别为。
/ | \
b c d
/ \
e f
7、对顺序栈,,则栈溢出。
8、对二叉树以某种遍历并加上线索的过程称为。
9、有序表是线性表(a1,a2,....an),

10、AOV-网结点和有向边分别表示.
二、选择题:(共20分)
1、下面关于线性表的叙述中,错误的是( )
(A)线性表采用顺序存储,必顺占用一片连续的存储单元。
(B)线性表采用顺序存储,便于进行插入和删除操作。
(C)线性表采用链接存储,不必占用一片连续的存储单元
(D)线性表采用链接存储,便于插入和删除操作。
2、用直接插入排序方法对下面四个序列进行排序(由小到大),元素比较次数最少的是( )
(A)94、32、40、90、80、46、21、69 (B)32、40、21、46、69、94、90、80
(C)21、32、46、40、80、69、90、94 (C)90、69、80、46、21、32、94、40
3、设森林F中有三棵树,第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )
(A)M1 (B)M1+M2 (C)M3 (D)M2+M3
4、用快速排序法对包含n个关键字的序列进行排序,最环情况下的执行时间为( )
(A)O(log2n) (B)O(n) (C)O(nlog2n) (D)O(n2)
5、以下数据结构中哪一个是线性结构?( )
(A)有向图(B)栈(C)线索二叉树(D)B树
6、单链表的每个结点中包括一个指针link,它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的单链表结点之后,下面的操作序列中哪一个是正确的?( )
A)q:=p^.link; p^.link:=q^.link;
B)p^.link:=q^.link; q:=p^.link;
C)q^.link:=p^.link; p^.link:=q;
D)p^.link:=q; q^.link:=q^.link;
7、以下哪一个不是队列的基本运算?( )
(A)从队尾插入一个新元素
(B)从队列中删除第i个元素
(C)判断一个队列是否为空
(D)读取队头元素的值
8、对线性表进行二分法查找,其前提条件是( )
(A)线性表以顺序方式存储,并且按关键码值排好序
(B)线性表以顺序方式存储,并且按关键码值的检索频率排好序
(C)线性表以链接方式存储,并且按关键码值排好序
(D)线性表以链接方式存储,并且按关键码值的检索频率排好序
9、下列哪一个关键码序列不符合堆的定义