Question

数据结构试题求解

题目比较多，希望有人解答一下了。我知道大家的时间都非常宝贵，希望能够抽出一点点的空闲给予解答（最好能写出理由），我将不胜感激，能答几道是几道吧，回答最多的给分酬谢。
谢谢！

选择题
( )1.设有两个长度为n的单向链表，结点类型相同。若以H1为表头指针的链表是非循环的，以H2为表头指针的链表是循环的，则________。
A. 对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O（1）。
B. 对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O（n）。
C.循环链表要比非循环链表占用更多的存储空间。
D. H1和H2是不同类型的变量。

（ ）2.在高度为h的完全二叉树中，_______.
A度为0的结点都在第h层上 。
B.第i（0≤i〈h-1）层上的结点都是度为2的结点。
C.第i（0≤i〈h-1）层上有2的（i-1）次方的结点。
D.不存在度为1的结点。

（ ）3.在一棵m阶B-树中，若在某叶子结点插入中一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是___________。
A.m-1 B.m C.｜ m/2 ｜ D. ｜m/2 ｜-1 （都是向上取值）

( )4.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行：
A.s->link=p->link; p->link=s; B.p->link=s->link;s->link=p;
C.q->link=s; s->link=p; D.p->link=s; s->link=q;

（ ）5.字符a,b,c,d的权值分别为2，3，4，11，则字符a的Huffman编码可能为：
A.11 B.010 C.0 D.其他

( )6.把一个指针s所指的新结点，作为非空双链表中q所指结点（中间结点）的直接后继插入，则正确的是________。
A.q->rlink=s;s->llink=q; q->rlink->llink=s;s->rlink=q->rlink;
B. s->llink=q; q->rlink=s; q->rlink->llink=s; s->rlink=q->rlink;
C. s->llink=q; s->rlink=q->rlink; q->rlink->llink=s; q->rlink=s;
D.以上都不对

( )7.已知广义表A=（（a,b,c）,(d,e,f)）,则Head(Tail(Head(Tail(A))))的值为_________
A.（d ） B.（e） C.c D.e

（ ）8.在一棵非空二叉树的中序遍历中，根结点的右边_______.
A.只有右子树上的所有结点
B.只有右子树上的部分结点
C.只有左子树上的所有结点
D.只有左子树上的部分结点

（ ）9.对n个顶点的带权连通图，它的最小生成树是指图中任意一个____________。
A.由n-1条权值最小的边构成的子图
B.由n-1条权值之和最小的边构成的子图
C.由n-1条权值之和最小的边构成的连通子图
D.由n个顶点构成的边的权值之和最小的连通子图

（ ）10.在一个空AVL树内，依次插入关键字：49，94，91，47，92，45，89，42，87，当删除关键码时，如果该关键码同时具有左右子女，则以其中序后继替代，则删除关键码91时的旋转类型是__________
A．左单旋 B. 左右单旋 C. 右单旋 D.其他情况

（ ）11.用整数1，2，3，4，5作为五个树叶的权值，可构造一棵带权路径长度值为_______的Huffman树。：
A.15 B.33 C.34 D.其他

Answer 1

选择题
( )1.设有两个长度为n的单向链表，结点类型相同。若以H1为表头指针的链表是非循环的，以H2为表头指针的链表是循环的，则________。
A. 对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O（1）。
B. 对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O（n）。
C.循环链表要比非循环链表占用更多的存储空间。
D. H1和H2是不同类型的变量。

第二个表删除最后指针的复杂度为O(1)。选B。这题应该是选错的，貌似。

（ ）2.在高度为h的完全二叉树中，_______.
A度为0的结点都在第h层上 。
B.第i（0≤i〈h-1）层上的结点都是度为2的结点。
C.第i（0≤i〈h-1）层上有2的（i-1）次方的结点。
D.不存在度为1的结点。

选A。B：都是出度为2的节点。C：将i=0带入，明显错误。D：叶子节点入度为1。

（ ）3.在一棵m阶B-树中，若在某叶子结点插入中一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是___________。
A.m-1 B.m C.｜ m/2 ｜ D. ｜m/2 ｜-1 （都是向上取值）

理论上，B-树在插入结点时，如果结点已满，需要将结点分裂为两个各占 M/2 的结点，但我没理解题目的“原有”是什么意思。
估计应该选B，我不确定。

( )4.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行：
A.s->link=p->link; p->link=s; B.p->link=s->link;s->link=p;
C.q->link=s; s->link=p; D.p->link=s; s->link=q;

已知q->link=p，那么插入应该执行s->link=p;q->link=s; 选C。

（ ）5.字符a,b,c,d的权值分别为2，3，4，11，则字符a的Huffman编码可能为：
A.11 B.010 C.0 D.其他

构造一个huffman树，4个字母编码数一定最多要3位，选B。

( )6.把一个指针s所指的新结点，作为非空双链表中q所指结点（中间结点）的直接后继插入，则正确的是________。
A.q->rlink=s;s->llink=q; q->rlink->llink=s;s->rlink=q->rlink;
B. s->llink=q; q->rlink=s; q->rlink->llink=s; s->rlink=q->rlink;
C. s->llink=q; s->rlink=q->rlink; q->rlink->llink=s; q->rlink=s;
D.以上都不对

先保证右链接正确，才能进行左链接赋值。正确的顺序是：
q->r->l=s; s->r=q->r; q->r=s; s->l=q;， 其中s->l=q的先后顺序无所谓。
选C。

( )7.已知广义表A=（（a,b,c）,(d,e,f)）,则Head(Tail(Head(Tail(A))))的值为_________
A.（d ） B.（e） C.c D.e

Tail(A)=((d,e,f))，Head(Tail(A))=(d,e,f)，Tail(Head(Tail(A)))=(e,f)
选D

（ ）8.在一棵非空二叉树的中序遍历中，根结点的右边_______.
A.只有右子树上的所有结点
B.只有右子树上的部分结点
C.只有左子树上的所有结点
D.只有左子树上的部分结点

选A，概念题。

（ ）9.对n个顶点的带权连通图，它的最小生成树是指图中任意一个____________。
A.由n-1条权值最小的边构成的子图
B.由n-1条权值之和最小的边构成的子图
C.由n-1条权值之和最小的边构成的连通子图
D.由n个顶点构成的边的权值之和最小的连通子图

选D，概念题。

（ ）10.在一个空AVL树内，依次插入关键字：49，94，91，47，92，45，89，42，87，当删除关键码时，如果该关键码同时具有左右子女，则以其中序后继替代，则删除关键码91时的旋转类型是__________
A．左单旋 B. 左右单旋 C. 右单旋 D.其他情况

没学过AVL……

（ ）11.用整数1，2，3，4，5作为五个树叶的权值，可构造一棵带权路径长度值为_______的Huffman树。：
A.15 B.33 C.34 D.其他

构造buffman树，3+6+10+15=34，选C。

Answer 2

(1)B
删第一个结点，时间复杂度分别为O(1)和O(n)
两个链表用相同类型变量，占相同大小空间
(2)C
第h层和第h-1层都有可能有叶子结点
第h-1层有可能存在度为1的结点
(3)A
参照B树的插入算法
(4)C
q是p的前驱结点
(5)B
(6)C
(7)D
Tail(A)=((d,e,f))
Head(Tail(A))=(d,e,f)
Tail(Head(Tail(A)))=(e,f)
(8)A
(9)D
前面三个不一定是生成树
(10)C
过程很复杂
(11)B
关键是建立起Huffman树

Answer 3

第9题选c把 c是k算法 d是p算法 但图由边构成 不是由点构成

Answer 4

1～5BCACB 5～10 CDADC 11 B

Answer 5

ttp://topic.csdn.net/u/20070110/14/1b45ee2c-e2cd-4622-94ed-1cffd89d1c5f.html