数据结构试题求解

来源：百度知道 编辑：UC知道 时间：2024/05/25 03:16:58
题目比较多，希望有人解答一下了。我知道大家的时间都非常宝贵，希望能够抽出一点点的空闲给予解答（最好能写出理由），我将不胜感激，能答几道是几道吧，回答最多的给分酬谢。
谢谢！

选择题
( )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->rlin

选择题
( )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