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

《数据结构》试卷八 一、填空题：（共２０分） 1、线性结构是数据元素的非空有限集,存在唯一的最后一个元素,除该元素外,其余元素有 直接后继. 2、Head[Tail[(b,k,m,g)]]= . 3、对n阶对称矩阵进行压缩存储,一般只存储 中元素,此时只需 个元素的存储空间. 4.带权路径长度最小的二叉树称做 . 5、若P指向单链表的尾结点时，则有P^.NEXT= 。 6、如图： a 该树中叶子结点,分支结点, 该树度分别为 。 / | \ b c d / \ e f 7、对顺序栈,当 时表示栈满.若再有新元素入栈,则栈溢出。 8、对二叉树以某种遍历并加上线索的过程称为 。 9、有序表是线性表(a1,a2,....an),并且表中元素关键字值ai.key有下列关系 10、AOV-网结点和有向边分别表示 . 二、选择题：（共20分） 1、下面关于线性表的叙述中，错误的是 （A）线性表采用顺序存储，必顺占用一片连续的存储单元。 B）线性表采用顺序存储，便于进行插入和删除操作。 C）线性表采用链接存储，不必占用一片连续的存储单元 D）线性表采用链接存储，便于插入和删除操作。 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是 （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 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是 （A）M1 B）M1+M2 C）M3 D）M2+M3 用快速排序法对包含n个关键字的序列进行排序，最环情况下的执行时间为 （A）O(log2n) B）O(n) C）O(nlog2n) D）O(n2) 以下数据结构中哪一个是线性结构? （A）有向图 B）栈 C）线索二叉树 D）B树 单链表的每个结点中包括一个指针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）读取队头元素的值 对线性表进行二分法查找，其前提条件是 （A）线性表以顺序方式存储，并且按关键码值排好序 B）线性表以顺序方式存储，并且按关键码值的检索频率排好序 C）线性表以链接方式存储，并且按关键码值排好序 D）线性表以链接方式存储，并且按关键码值的检索频率排好序 下列哪一个关键码序列不符合堆的定义? （A）A、C、D、G、H、M、P、Q、R、X B）A、C、M、D、H、P、X、G、Q、R C）A、D、P、R、C、Q、X、M、H、G D）A、D、C、M、P、G、H、X、R、Q | J (A) A (B) A / \ / \ B E B E / / \