数据结构试卷及答案

选择题（查找排序不考）1．下面关于线性表的叙述错误的是（ D )。(A） 线性表采纳顺序存储必须占用一片连续的存储空间（B） 线性表采纳链式存储不必占用一片连续的存储空间(C） 线性表采纳链式存储便于插入和删除操作的实现（D） 线性表采纳顺序存储便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构,则该哈夫曼树中总共有（ B ）个空指针域。（A）2m—1(B)2m(C）2m+1(D）4m3．设顺序循环队列 Q[0：M—1］的头指针和尾指针分别为 F 和 R，头指针 F 总是指向队头元素的前一位置，尾指针 R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。（A) R-F（B） F—R(C) (R—F+M）%M （D） （F—R+M）％M4．设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为 CABD，则后序遍历该二叉树得到序列为（ A ）。(A) BADC（B)BCDA（C） CDAB（D） CBDA5．设某完全无向图中有 n 个顶点，则该完全无向图中有（ A ）条边.（A） n(n-1）/2 （B） n（n-1）（C) n2 （D） n2—16．设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（ C ）。(A) 9(B） 10 （C) 11 （D） 127．设某有向图中有 n 个顶点,则该有向图对应的邻接表中有（ B）个表头结点。(A) n-1 （B) n(C） n+1（D） 2n-18．设一组初始记录关键字序列（5，2，6,3,8）,以第一个记录关键字 5 为基准进行一趟快速排序的结果为( C ）。（A） 2，3，5，8,6（B) 3,2，5,8，6(C） 3，2，5，6,8（D） 2,3，6，5，81。D2。B3.C4。A5。A6。C7。B8。C1．设某数据结构的二元组形式表示为A= （ D,R) ， D= ｛ 01 ， 02 ， 03 ， 04 ， 05 ， 06,07 ， 08 ， 09} ， R={r ｝ ， r={ 〈 01 ， 02 〉 ,〈01，03〉，〈01，04〉，〈02，05〉,〈02，06〉,〈03，07>,〈03,08〉，<03,09〉}，则数据结构 A 是( B）。(A） 线性结构（B） 树型结构（C） 物理结构(D) 图型结构2．下面程序的时间复杂为（B ）for（i=1,s=0; i〈=n; i++）｛t=1；for(j=1；j〈=i;j++）t=t*j；s=s+t;｝（A） O(n)(B） O(n2） (C) O（n3）（D） O（n4）3．设指针变量 p 指向单链表中结点 A，若删除单链表中结点 A,则需要修改指针的操作序列为（ A ）。(A） q=p-〉next;p-〉data=q—>data；p—〉next=q—〉next;free(q)；（B） q=p—〉next;q->data=p->data；p—>nex...