级《数据结构》A卷及答案.docVIP

一．判断题 1．线性结构的基本特征是每个结点至多只有一个直接前驱和一个直接后继。 2．队列的特点是先进先出，优先级队列也不例外，同样也是先进先出。 3．在栈为空的情况下，不能作出栈操作，否则会产生下溢。 4．二叉树中每个结点的两棵子树的高度差不大于1。 5．广义表((2),(2))的表尾是((2))。 6．如果树用二叉树链表表示，则判断某个结点是不是树叶的条件是该结点左、右两个指针域的值都为空。 7．若邻接表中有奇数个边结点，则该图一定为有向图。 8．9阶B-树中，除根以外的任何一个非叶子结点中的关键字数目均在5～9之间。 9．直接插入排序是一种稳定的排序方法。 10．散列表的装载因子表明表的装满程度，它与预设的最大桶长有关。二．单项选择题 1．下列关于存储结构的叙述中，正确的是_________。 A、顺序存储方式只能用于存储线性结构。 B、线性表的逻辑顺序与存储顺序总是一致的。 C、散列法存储的基本思想是由关键字的值决定数据的存储地址。 D、静态链表具有动态链表的优点，它存取表中第i个元素的时间与i无关。 2．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移 个元素。 A、n-i B、n-i-1 C、n-i+1 D、i 3．设n个元素的进栈序列是a1，a2，a3，…，an，出栈序列是1，2，3，…，n，若a3=1,则a1的值是 。 A、可能是2 B、一定是2 C、不可能是2 D、不可能是3 4．假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是__ 。 A、f+1==r B、r+1==f C、f==0 D、f==r 5．在非空有头结点双向循环链表中，设前驱指针为lLink，后继指针为rLink，若要删除非头结点指针P所指结点的后继，则执行的语句为 。 A、p - lLink - rLink = p - rLink; p - rLink -lLink = p - lLink; B、p - rLink - lLink = p - lLink; p - lLink -rLink = p - rLink; C、p - lLink = p - lLink - lLink; p - lLink - rLink = p; D、p - rLink = p - rLink - rLink; p - rLink - lLink = p; 6．数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为__________。 A、1125 B、1145 C、1120 D、1140 7． 设栈s和队列Q的初始状态为空， 元素b1 ，b2， ，b3 ，b4 ，b5和b6 依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是b2 ，b4 ，b3 ，b6 ，b5 ，b1 ，，则栈S的容量至少应该是 。 A、3 B、4 C、5 D、其它 8．由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为 。 A、 53 B、 48 C、 72 D、 24 9．如将一棵有n个结点的完全二叉树按顺序存放方式，存放在下标编号为0, 1,…, n-1的一维数组中，设某结点下标为k(k0)，则其双亲结点的下标是 。 A、(k-1)/2 B、(k+1)/2 C、k/2 D、k-1 10．在一棵高度小于3的二叉树中，若结点的前序序列为ABCDEF，则结点的中序序列有可能为 。 A、DCEBAF B、CBDAFE C、BCDAFE D、FCADBE 11．在下面几组关键字中,哪个是最小堆_______。 A、{05,13,55,94,17,46,42} B、{05,42,13,55,94,17,46} C、{05,42,17,94,55,13,46} D、{94,42,55,01,17,13,46} 12．有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉有哪些信誉好的足球投注网站树，若希望高度最小，则应选择下面哪个序列输入 。 A、45，24，53，12，37，96，30 B、37，24，12，30，53，45，96 C、