数据结构期中复习答案

《数据结构期中复习答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构期中复习答案第一部分试题一、单项选择题（每小题2分，共50分）1.算法的时间复杂度取决于（B）。A.待处理数据的初态B.问题的规模C.问题的规模和待处理数据的初态2.—种抽象数据类型包括数据和（B）两个部分。A.数据类型B.操作C.数据杣象D.类型说明3.当需要用一个形式参数直接改变对应实际参数的值时，则该形式参数应说明为（C）。A.基本类型B.结构类型C.指针型D.数组型4.一个记录r理论上占存的存储空间的大小等于所有域类型长度之和，实际上占柯的存储空间的大小即记录长度为（D）oA.所有域长度之和B.最大域所占字节长度C.任意一个域长度D.sizeof（r）的值5.以下说法正

2、确的是（A）。A.数据结构的逻辑结构独立于其存储结构。B.数据结构的存储结构独立于该数据结构的逻辑结构。C.数据结构的逻辑结构唯一地决定了该数据结构的存储结构。D.数据结构仅由其逻辑结构和存储结构决定。6.线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以7.在一个长度为n的顺序表的表尾插入一个新元素的渐进时问复杂度为（B）。A.O（n）B.0（1）C.0（n）D.0（log2n）8.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（A）。A.0（n）B.0（n/2）C.0（1）

3、D.0（n2）9.带失结点的线性链表L为空的判定条件是什么？（B）A.L==NULL;B.L->next==NULL;C.L->next==L;D.L!=NULL;10.设线性链表中结点的结构为（data，next）。己知指针q所指结点是指针p所指结点的直接前驱，若在叫与邙之间插入结点*s，则应执行下列哪一个操作？（B）A.s-〉next-p->next;p-〉next-s;B.q->next-s;s-〉next-p;C.p->next=s->next;s->next=p;D.p->next=s;s->next=q;11.设线性链表中结点的结构为（data,next）。已知指针p所指结

4、点不是尾结点，若在*p之后插入结点什，则应执行下列哪一个操作？（D）A.s-〉next-p;p-〉next-s;B.p-〉next-s;s~>next-p;C.s-〉next-p-〉next;p-s;D.s-〉next-p->next;p->next-s;12.非空的循环单链表Head的尾结点（由p所指向）满足什么条件？（C）A.p->next==NULL;B.p==NULL;C.p->next—Head;D.p二二Head;13.利用双向链表作线性表的存储结构的优点是什么？（B）A.便于进行插入和删除的操作B.提高按关系査找数据元素的速度C.节省空间D.便于销毁结构释放空间1.带表头

5、的双向循环链表空表的表示是什么？（B）A.Head=NULL;B.Head-〉next=Head~>prior=HeadC.Head=Head->nextD.Head-〉next=Head->prior=NULL15.栈的插入和删除操作在（A）进行。A.栈顶B.栈底C.任意位置D.指定位置16.若让元素1,2,3依次进栈，则出栈次序不可能出现（c）种情况。A.3,2，1B.2,1，3C.3,1，2D.1,3,217.在一个顺序存储的循环队列中，队头指针指向队头元素的（C）位置。A.前一个B.后一个C.当前D.后面18.从一个顺序存储的循环队列中删除一个元素时，首先需要（C）。A.队头指

6、针加一B.队头指针减一C.取出队头指针所指的元素D.取出队尾指针所指的元素19.假定一个顺序存储的循环队列的队爻和队尾指针分别为front和rear，则判断队空的条件为（D）0A-front+1==rearB-rear+1==frontC.front==0D.front==rear20.为增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的（D）分别设在这片内存空间的两端.A.长度B.深度C.栈顶D.栈底21.在一棵树中，（C）没有前驱结点。A.分支结点B.叶子结点C.树根结点D.空结点22.—棵具存35个结点的完全二叉树的高度为（B）。假定空树的高度为

7、0。A.5B.6C.7D.823.把一棵树转换为二义树后，这棵二义树的形态是（D）。A.有多种B.有多种，但根结点都没有左孩了C.有多种，但根结点都没有右孩了•D.唯一的24.利用n个位作为叶结点的权生成的哈夫曼树屮共包含有（D）个结点。A.nB.n+1C.2*nD.2*n~l25.利用3,6,8,12这四个值作为叶了结点的权，生成一棵哈夫曼树，该树的带权路径长度为（A）。A55B29C58D38二、填空（共20分，广8小题每空1分，第9小题4