数据结构题库

东华大学学年第学期期末试题2010〜20H1踏实学习，弘扬正气；诚信做人，诚实考试；作弊可耻，后果自负课程名称数据结构使用专业计算机科学与技术类班级姓名学号试题--四五六七八九十总分—•得分

一、单项选择题（每空分，本题共分）240数据结构是（）

1.D o、数据、数据对象A B、数据对象上的关系、由数据对象和其上的关系构成的二元组C D一个算法应该是（）2B程序问题求解步骤的描述A.B.数据结构+程序以上都不对C.D.线性表是具有个（）的有限序列（）3n Cn0表元素字符数据元素数据A.B.C.D.项信息项E.衡量查找算法好坏的依据是（）4Ao关键字和给定值进行过比较的记录个数的平均值占用的辅助空间A.B.数据元素移动次数上述说法都不对C.D.稳定的排序算法是（）

5.Do排序后数据元素的个数不变排序后数据元素的位置不变A.B.排序后数据元素间的关系不变上述说法都不对C.D.若一个链栈的栈顶指针用表示，当进行退栈时所进行的指针操作为（）

6.top AoA.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.一个个顶点的连通无向图，其最小生成树的边数为（）9n A；A.n-1B.n C.n+1D.nlogn有个叶子的哈夫曼树的结点总数为（）

10.n Do不确定A.B.2n C.2n+l D.2n-l在单链表指针为的结点之后插入指针为的结点，正确的操作是（）

11.p sCA.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..下列关于网的叙述中，不正确的是（）13AOE B关键活动不按期完成就会影响整个工程的完成时间A.任何一个关键活动提前完成，那么整个工程将会提前完成B.所有的关键活动提前完成，那么整个工程将会提前完成C.某些关键活动提前完成，那么整个工程将会提前完成D.若需在（）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方.

14.O Mogn法是（）C o.快速排序堆排序.归并排序直接插入排序A B,C D.关键路径是事件结点网络中（）

15.A从源点到汇点的最长路径从源点到汇点的最短路径A.B.最长回路最短回路C.D..当一个有个顶点的有向图用邻接矩阵表示时，顶点的度是（）16N AVi D■

11.1n力，力A Al4,21M Zu lA.t-1B.C.t-l D.t-1+对个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）

17.N A（）（）A.N+l/2B.N/2C.N D.[1+N*N]/2将一棵树转换为孩子一兄弟链表表示的二叉树贝亚的后根序遍历是的（）

18.t h,h B前序遍历中序遍历后序遍历层次遍历A.B.C.D.具有个关键字的有序表，折半查找的平均查找长度（）

19.12AA.

3.1B.4C.

2.5D.5在双向链表指针的结点前插入一个指针的结点操作是（）

20.p qC二；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+425有个元素，其入栈次序为在各种可能的出栈次序中，以元素最先出栈

1.5A,B,C,D,E,C,D（即第一个且第二个出栈）的次序有哪几个？C D.假设一棵二叉树的前序序列为和中序序列为请画出该树2EBADCFHGIKJ ABCDEFGHIJKo依次输入表（）中的元素,生成一棵二叉排序

3.30,15,28,20,24,10,12,68,35,50,46,55试画出生成之后的二叉排序树；对该二叉排序树作中序遍历，试写出遍历序歹；12U假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度

3.请问快速排序适合采用什么样的存储结构，并简要说明理由

4.试证明在一个有个顶点的完全图中，生成树的数目至少有5n2nT-l

三、算法题5分+15分+15分,本题共35分.请填空完成下面求树的带权路径长度的类算法1Huffman WPLC［说明］其中为树的根结点的指针，为工作栈，、和ht SClearstackS PushS,p PopS分别为置栈空、指针进栈、出栈和判栈空的函数EmptystackS pTypedeffloat weight;Typedef struct node{weight w;structnode*Lchild,*Rchild,parent;Jhnode,*hlink〃求树的weight CaLWPLhlink htHuffman WPL{hlink p;weight num=

0.0;ClearstackS;______CD________;While!EmptystackSP=PopS;while2{if3num+=p-w;if4PushS p-Rchild;95:returnnum;已知不带头结点的线性链表链表中结点构造为其中为数据域,为指

2.list,data next,data next针域请写一算法，将该链表按结点数据域的值的大小从小到大重新链接要求链接过程中不得使用除该链表以外的任何链结点空间二叉树以链方式存储，有三个域，数据域左右孩子域树根由指向

3.data,lchild,rchild tree请编写算法要求按层次从上到下，同层次从左到右遍历树请写出算法根据完全二叉树的顺序存储结构，构造其二叉链表结构

4.学年第一学期期末试题2009------------------2010踏实学习，弘扬正气；诚信做人，诚实考试；作弊可耻，后果自负课程名称数据结构使用专业计算机

1、______

2、______、、、

345、、、6______

7、______

8910、、、1314151k_______

12、______

16、______、____

18、

19、

20、17班级计算机科学与技术类姓名学号试题四五六七八九十总分■—-得分

一、选择

二、综合应用。