数据结构题库

PAGE1注意：填写内容不要超出以上格式,第二页的边距和第一页一样出题人(签名)：__________室负责人(签名)：_________东华大学2010~2011学年第1学期期末试题踏实学习，弘扬正气；诚信做人，诚实考试；作弊可耻，后果自负。课程名称数据结构使用专业计算机科学与技术类班级_____________________姓名________________学号__________试题得分一二三四五六七八九十总分一、单项选择题（每空2分，本题共40分）数据结构是（D）。A、数据 B、数据对象C、数据对象上的关系 D、由数据对象和其上的关系构成的二元组2一个算法应该是（

B）。A．程序

B．问题求解步骤的描述

C．数据结构+程序

D．以上都不对3线性表是具有n个（C）的有限序列（n>0）。A．表元素

B．字符

C．数据元素

D．数据项

E．信息项4衡量查找算法好坏的依据是（A）。A．关键字和给定值进行过比较的记录个数的平均值

B．占用的辅助空间C．数据元素移动次数

D．上述说法都不对5.稳定的排序算法是（D）。A．排序后数据元素的个数不变

B．排序后数据元素的位置不变C．排序后数据元素间的关系不变

D．上述说法都不对6．若一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为(A)。A.top->next=top;B.top=top->next;C.top=top->data;D.top->next=top->next->next;7．连续存储设计时，存储单元的地址（

A）。A.一定连续

B．一定不连续

C．不一定连续

D．部分连续，部分不连续8．以下属于逻辑结构的是（

C

）。A．顺序表

B.哈希表

C.有序表

D.

单链表9一个n个顶点的连通无向图，其最小生成树的边数为（A）。A．n-1B．nC．n+1D．nlogn；10．有n个叶子的哈夫曼树的结点总数为（D）。A．不确定B．2nC．2n+1D．2n-111．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（

C

）。A．p->next=s->next;p->next=s;

B．p->next=s;p->next=s->next;C．s->next=p->next;p->next=s;

D．p->next=s;s->next=p->next;12．引入线索二叉树的目的是（A）A．加快查找结点的前驱或后继的速度

B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲

D．使二叉树的遍历结果唯一13．下列关于AOE网的叙述中，不正确的是（

B

）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成.14.若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C）。A.快速排序B.堆排序C.归并排序D.直接插入排序15.关键路径是事件结点网络中（A）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路16.当一个有N个顶点的有向图用邻接矩阵A表示时，顶点Vi的度是（D）。A．B．C．D．+17.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A)A．（N+1）/2B.N/2C.ND.[（1+N18.将一棵树t转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h的（B）A．前序遍历B．中序遍历C．后序遍历D.层次遍历19.具有12个关键字的有序表，折半查找的平均查找长度（A）A.3.1B.4C.2.520.在双向链表指针p的结点前插入一个指针q的结点操作是（C）。A.p->prior=q;q->next=p;p->prior->next=q;q->prior=q；B.p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;C.q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;D.q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;二、综合应用题(4分+5分+6分+6分+4分,本题共25分)1．有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？2．假设一棵二叉树的前序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。3．依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树(1)试画出生成之后的二叉排序树;(2)对该二叉排序树作中序遍历，试写出遍历序列;(3)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。4．请问快速排序适合采用什么样的存储结构，并简要说明理由。5．试证明在一个有n个顶点的完全图中，生成树的数目至少有2n-1-1。三、算法题(5分+15分+15分,本题共35分)1.请填空完成下面求Huffman树的带权路径长度（WPL）的类C算法。[说明]其中ht为树的根结点的指针，S为工作栈，Clearstack(S)、Push(S,p)、Pop(S)和Emptystack(S)分别为置栈空、指针p进栈、出栈和判栈空的函数。Typedeffloatweight;Typedefstructnode{weightw;structnode*Lchild,*Rchild,*parent;}hnode,*hlinkweightCal_WPL(hlinkht)//求Huffman树的WPL{hlinkp;weightnum=0.0;Clearstack(S);(1);While(!Emptystack(S)){P=Pop(S);while((2)_____)｛if((3)_____)num+=p->w;if((4)_____)Push(S,p->Rchild);(5)_____;}}return(num);}2.已知不带头结点的线性链表list，链表中结点构造为（data、next），其中data为数据域，next为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。3.二叉树以链方式存储，有三个域，数据域data，左右孩子域lchild,rchild。树根由tree指向。请编写算法要求按层次从上到下，同层次从左到右遍历树。4．请写出算法根据完全二叉树的顺序存储结构，构造其二叉链表结构。

20092010学年第一学期期末试题踏实学习，弘扬正气；诚信做人，诚实考试；作弊可耻，后果自负课程名称数据结构使用专业计算机班级计算机科学与技术类姓名学号试题得分一二三四五六七八九十总分一、选择1、2、3、4、5、6、