2022年2022年计算机数据结构c语言期末试题 .pdf

《2022年2022年计算机数据结构c语言期末试题 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机数据结构c语言期末试题 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、所有试卷资料免费下载第 - 1 - 页 共 6 页考试日期： 2006 年 4 月 30 日一、选择题（ 2 分 8 = 16分）1. 以下数据结构中，是非线性数据结构的是。A. 树B. 字符串C. 数组D. 栈2. 下列程序段的渐进时间复杂度为。for( int i=1;i=n;i+) for( int j=1;j= m; j+) Aij = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 3. 数组 A0 5，06的每个元素占5 个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A5 ，5的地址为。A. 1175 B. 1180 C

2、. 1205 D.1210 4. 以下关于链式存储结构的叙述中，是不正确的。A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i 个结点的存储地址D.插入、删除操作方便，不必移动结点5. 设栈 S 和队列 Q 的初始状态为空，元素e1、e2、e3、e4、e5 和 e6 依次通过栈S，一个元素出栈后即进入队列Q， 若 6 个元素出队的顺序是e2、 e4、 e3、 e6、 e5、 和 e1， 则栈 S 容量至少应该是。A. 6 B. 4 C. 3 D. 2 6. 以下关于广义表的叙述中，正确的是。A. 广义表是 0 个或多个单

3、元素或子表组成的有限序列B. 广义表至少有一个元素是子表C. 广义表不可以是自身的子表D. 广义表不能为空表7. 先序遍历序列与中序遍历序列相同的二叉树为。A. 根结点无左子树的二叉树B.根结点无右子树的二叉树C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 所有试卷资料免费下载第 - 2 - 页 共 6 页8. 在有 n

4、个叶子结点的霍夫曼树中，其结点总数为：。A. n B. 2n C. 2n +1 D. 2n - 1 二、填空题（ 2 分 5 =10 分）1. 一个算法具有5 个特性：、有零个或多个输入，一个或多个输出。2. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。3. 字符串“ abcd”中共有个长度大于0 的字串。4. 广义表 list= （5，（3， 2，（14， 9， 3） ，（） ， 4） ， 2，（6， 3， 10） ） 的长度及深度分别为和。5. 具有 n 个结点的完全二叉树的高度为三、 名词解释（ 24 分）（1）抽象数据类

5、型（2）完全二叉树（3）堆四、简答题（ 30 分）1. 请对线性表进行顺序存储和链式存储的特点作比较。2. 假设有一个适当大小的栈S，输入栈的序列为A，B，C，D，E。问：（1）能否得到下列的输出序列： B，C，D，E，A； E，A，B，C ，D；E，D， C ，B，A。（2）写出所有可能正确的输出序列。3. 设一棵二叉树后序遍历序列为DGJHEBIFCA ，中序遍历序列为DBGEHJACIF ，要求：（1）画出该二叉树；（2）写出该二叉树的先序遍历序列；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

6、- - - - 第 2 页，共 6 页 - - - - - - - - - 所有试卷资料免费下载第 - 3 - 页 共 6 页（3）画出该二叉树对应的森林。五、 算法设计题（20 分）1. 填充下列算法的空白处，完成在不带表头结点的单链表第i 个结点之前插入新元素x 的操作。（8分）int Insert ( constint x, const int i ) /在链表第i 个结点处插入新元素xlistNode *p = first ; int k = 0;while ( p != NULL & k i -1 ) ; k+; /找第 i-1 个结点if ( p = NULL& first !=

7、NULL ) /非空表且链短，找不到i-1 个节点cout “ Invalid position n” ; return 0; listNode *newnode= new Node(x, NULL ); if ( first = NULL| i = 0 ) /插入空表或插在非空表前newnodelink = first ; if ( first = NULL ) last = newnode ; / 修改首指针 else /插在表中或末尾; if ( plink = NULL ) last = newnode ; return 1;/正常插入，函数返回1 名师资料总结 - - -精品资料欢迎

8、下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 所有试卷资料免费下载第 - 4 - 页 共 6 页2. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法（12 分） ：（1）统计二叉树中叶子结点的个数；（2）交换每个结点的左子女和右子女。选做题（ 20 分）（西安电子科技大学2006 年硕士研究生入学考试最后一题）假设以数组seq0m-1存放循环队列中的元素，同时设变量rear 和 quelen 分别指示循环队列中的队尾元素的位置和内含元素的个数。请给

9、出：（1）给出循环队列的队满条件和队空条件；（2）写出相应的入队列和出队列的算法，并分别分析其时间代价；（3）如果用数组sequmn来存放循环队列中的元素，则（2）中的入队列和出队列的算法中的哪些语句要修改？如何修改？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 所有试卷资料免费下载第 - 5 - 页 共 6 页哈尔滨工业大学二 00 一年研究生考试试题考试科目：数据结构报考专业：计算机科学与技术一填空（总分： 10 分，每一

10、题2 分）1 对于一个具有n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为_, 在给定为 x 的结点后插入一个新结点的时间复杂度为_。2 广义表（ a， （a，b） ，d，e，( (I,j,), k) ）的长度是 _, 深度是 _。3 对于一个具有n 个结点的二员树，当它为一棵_二元树时具有最小高度，当它为一棵_时，具有最大高度。4 在顺序文件中，要存取第I 个记录，必须先存取_个记录。5 求最短路径的dijkstra 算法的时间复杂度为_。二选择填空： （总分 10 分，每小题2 分）1 若某线性表最常用的操作是存取任意指定序号的元素和最后进行插入和删除运算，则利用 _存

11、储方式最节省时间。（1）顺序表；（2）双链表；（3）头结点的双循环链表；（4）单循环链表2 在一棵三元树中度为3 的结点数为2 个，度为 2 的结点数为1 个，度为 1 的结点数为2 个，则度为 0 的结点数为 _个（1） 4 （2）5 （3）6 （4）7 3 在一个图中， 所有顶点的度数之和等于所有边数_倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的_倍（1）1/2 （2）2 （3）1 （4）4 4 下列排序算法中，_,排序在某趟结束后不一定能选出一个元素放到其最终的位置上。（1）选择（2）冒泡（3）归并（4）堆5 散列文件使用散列函数将记录的关键字值计算转化为记录的关键字值计

12、算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的_方法是散列文件的关键。（1）散列函数（2）除余法中的质数（3）冲突处理（4）散列函数和冲突处理三回答下列问题（总分 15 分，每小题3 分）1数据结构与数据类型有什么区别？2什么是循环队列？3简述线索二元树的概念。4何为有向图的遍历？5什么是索引顺序文件？四分别画出和下列树对应的各个二元树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 所有试卷资料免费下载第 -

13、6 - 页 共 6 页五试设计一个算法，判断链表L 是否是递减的。六判断以下序列是否为堆，如果不是，则把它调整为堆。(1) (12,24,33,65,33,56,48,92,86,70) (2) (25,56,20,23,40,38,29,61,35,76,28,100) 七设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区Omaxsize-1, 为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。八假设用于通讯的电文仅有6 个字母 abcdef 组成，字母在电文中出现的频率分别为7，19，5，16，42，11。试为这 6 个字母设计哈夫曼编码九试写一算法，判断以邻接表方式存储的有向图中是否存在有顶点Vi到顶点 Vj的路（ij ） 。注意：算法中涉及的图的基本操作必须在存储结构上实现。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -