下载文档原格式
东北林业大学 2005－2006学年第二学期考试试题 学院：信息学院 教研室（学科）主任：第3 页共 3 页 考试科目： 数据结构（A ）考试时间：120分钟 试卷总分 100分 题号 一 二 三 四 五 总分 得分 评卷 教师 一、单项选择题（在每个小题四个备选答案中选出一个正确答案，填在题末的括号中）（本大题共10小题，每小题1.5分，总计15分） 1、从逻辑上可以把数据结构分为（ ）两大类。
A ．动态结构、静态结构 B ．顺序结构、链式结构 C ．线性结构、非线性结构 D ．初等结构、构造型结构 答案（ ） 2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A ．顺序表 B ．双链表 C ．带头结点的双循环链表 D ．单循环链表 答案（ ） 3、循环队列A[0..m-1]存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是( )。
A.(rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 答案（ ） 4、串的长度是指（ ）。
A ．串中所含不同字母的个数 B ．串中所含字符的个数 C ．串中所含不同字符的个数 D ．串中所含非空格字符的个数 答案（ ） 5、设广义表L=（（a,b,c ）），则L 的长度和深度分别为（ ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3 答案（ ） 6、二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK ；中序遍历: HFIEJKG 。
该二叉树根的右子树的根是：( )A. EB. FC. GD. H答案（ ）7、深度为h 的满m 叉树的第k 层有（ ）个结点。
(1=<k=<h)A ．m k-1B ．m k -1C ．m h-1D ．m h -1答案（ ）8、关键路径是事件结点网络中（ ）。
计算机科学与技术专业《数据结构》实验指导书关于实习步骤的要求和建议从以往的教学事先实习的经验来看，在初学阶段执行严格的实习步骤规范（包括上机操作规范），机时利用率会大大提高，有助于养成良好的程序编制风格，培养严谨、科学、高效的工作方式。
在以往的教学实践中，经常发现很多学生抱怨说，化了两个小时才找出一个错误，甚至一无所获。
他们不明白造成这种情况的原因，正是他们自己。
有的学生不屑于按实习步骤规范去做，甚至对于实习步骤的要求和建议看都不看一遍，认为那是浪费时间，这是及其害的。
实习步骤规范不但可以培养科学化的工作作风，而且还能有效地避免错误。
具体的步骤机规范如下：1．问题分析与系统的结构设计充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。
按照以数据结构为中心的原则划分模块，即定义数据结构及其在这些结构之上的操作，使得对数据结构的存取通过这些操作加以实现。
在这个过程中，要综合考虑系统功能。
要考虑系统结构清晰、合理、简单并且易于调试。
最后写出每个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。
2．详细设计和编码详细设计的目的是对子程序（过程或函数）的进一步求精。
用 IF 、 WHILE和赋值语句等，以及自然语言写出算法的框架。
利用自然语言的目的是避免陷入细节。
在编码是，可以对详细设计的结果进一步求精，用高级语言表示出来。
程序的每一行最好不超过 60 个字符。
每个子程序（或过程、函数）通常不要太长，以 40 行为宜。
子程序（或过程、函数）包含的程序行数太多，易于造成理解的困难。
控制IF 、WHILE 等语句的连续嵌套的深度。
程序的目的性必须明确。
对每一段程序完成的作用，除非常明显的除外（如：x = x + 1; 注释为 x 加 1，没有什么意义），都应加以注释。
这会对程序的调试提供很多方便。
另外，根据情况可以设立若干调试点，即输出若干信息，用于验证和你的设想是否一致。
2022年东北林业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。
A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。
A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、单链表中，增加一个头结点是为了（）。
A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。
A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
![数据结构与算法-东北林业大学 数据结构演示文稿6[1]](https://img.taocdn.com/s1/m/4d7984d3b9f3f90f76c61b7a.png)
2003-2004学年第二学期数据结构期终试卷（A卷）（考试时间100分钟）班级姓名学号得分一、单项选择题（本大题共15小题，第小题2分，共30分）在每小题列出的四个选项中只有一个符合题目要求，请将其代码填在题后的括号内。
错选或未选均无分。
1. 算法必须具备输入、输出和[ C ]A. 计算方法B. 排序方法C．解决问题的有限运算步骤 D. 程序设计方法2. 有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是[ A ]A.访问第i个节点（1≤i≤n）B.在第i个节点后插入一个新节点（1≤i≤n）C.删除第i个节点（1≤i≤n）D.将n个节点从小到大排序3．单链表的存储密度[ C] A．大于1 B. 等于1C．小于1 D. 不能确定4．设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是[ B] A．23415 B. 54132C．23145 D. 154325. 循环队列SQ的存储空间是数组d[m]，队头、队尾指针分别是front和rear，则执行出队后其头指针front值是[ D ] A．front=front+1 B. front=(front+1)%(m-1)C. front=(front-1)%mD. front=(front+1)%m6. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是[ B ]A. O(1)B. O(n)C. O(n2)D. O(nlogn)7. 设二维数组A[0..m-1][0..n-1]按行优先顺序存储，则元素A[i][j]的地址为A．LOC(A[0][0])+(i*m+j) B．LOC(A[0][0])+(i*n+j)C.LOC(A[0][0])+[(i-1)*n+j-1]D. LOC(A[0][0])+[(i-1)*m+j-1]8. 一个非空广义表的表头[ D ]A．一定是子表 B. 一定是原子C．不能是子表 D. 可以是原子，也可以是子表9．具有n个节点的完全二叉树的深度为[ A ] A．⎡log2(n+1)⎤ -1 B. log2n+1C. log2nD. ⎣log2n⎦10. 若要惟一地确定一棵二叉树，只需知道该二叉树的[ D ]A．前序序列 B. 中序序列C．前序和后序序列 D. 中序和后序序列11．在一个无向图中，所有顶点的度数之和等于图的边数的倍[ C ] A．1/2 B. 1C. 2D. 412. 拓扑排序运算只能用于[ C ]A．带权有向图 B. 连通无向图C．有向无环图 D. 无向图13．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是[ D ] A．希尔排序 B. 冒泡排序C．插入排序 D. 选择排序14．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是[ C ] A．堆排序 B. 冒泡排序C．直接选择排序 D. 快速排序15．二分查找要求节点[ A ] A．有序、顺序存储 B. 有序、链接存储C．无序、顺序存储 D. 无序、链接存储二、填空题（本大题共10小题，每小题2分，共20分）不写解答过程，将正确的答案写在每小题的空格内。
贵州大学理学院数学系信息与计算科学专业《数据结构》期末考试试题及答案(2003-2004学年第2学期)一、单项选择题1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。
(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。
for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。
（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。
（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。
（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9． Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。
青书学堂系统东北林业大学-数据结构所有答案27问答题头指针和头结点在线性表的链式存储结构中的作用是什么本题150分答案是：标准答案：头指针具有标识作用,故常用头指针冠以链表的名字;头结点的数据域中不存储线性表的数据元素,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对开始结点进行统一处理。
26问答题交换排序的基本思想是什么本题150分答案是：标准答案：交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
单选题在单链表n1C、 OmnD、 Om*n答案是：标准答案：D单选题线性表的顺序存储结构是一种的存储结构,线性表的链式存储结构是一种存储结构。
本题30分A、随机存取B、顺序存取C、索引存取D、散列存取答案是：标准答案：A单选题数据结构只是研究数据的逻辑结构和物理结构,这种观点。
本题30分A、正确B、错误C、前半句对,后半句错D、前半句错,后半句对单选题数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储比顺序存储要。
本题30分A、低B、高C、相同D、不好说答案是：标准答案：B单选题算法分析的主要方法。
本题30分A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性答案是：标准答案：A单选题数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称之为。
本题30分A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构答案是：标准答案：C单选题某班级的学生成绩表中查得张三同学的各科成绩记录,其中数据结构考了90分,那么下面关于数据对象、数据元素、数据项描述正确的是本题30分A、某班级的学生成绩表是数据元素,90分是数据项B、某班级答案是：标准答案：C单选题数据结构这门学科是针对什么问题而产生的本题30分A、针对非数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针答案是：标准答案：A22问答题顺序查找的基本思想是什么本题150分答案是：标准答案：顺序查找是一种最简单的查找方法。
东北林业大学2005－2006学年第二学期考试试题考试科目：数据结构（A）评分标准及参考答案一、单项选择题（在每个小题四个备选答案中选出一个正确答案，填在题末的括号中）（本大题共10小题，每小题1.5分，总计10分）(选对1个题给1.5分，选错1个题不给分)1、从逻辑上可以把数据结构分为（）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构答案（C）2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表答案（ A ）3、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。
A.(rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front答案（ A ）4、串的长度是指（）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数答案（ B）5、设广义表L=（（a,b,c）），则L的长度和深度分别为（）。
A. 1和1B. 1和3C. 1和2D. 2和3答案（C）6、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历: HFIEJKG 。
该二叉树根的右子树的根是：( )A. EB. FC. GD. H答案（ C ）7、深度为h的满m叉树的第k层有（）个结点。
(1=<k=<h)A．m k-1 B．m k-1 C．m h-1 D．m h-1答案（A）8、关键路径是事件结点网络中（）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径C．最长回路 D．最短回路答案（A）9、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。
东北林业大学 2003－2004学年第二学期考试试题 考试科目：数据结构 考试时间：120分钟 试卷总分85分
一、单项选择题（在每个小题四个备选答案中选出一个正确答案，填在题末的括号中）（本大题共10小题，每小题2分，总计20分） 1．设输入序列为a ，b ，c ，d ，借助一个栈得到的输出序列不可能是（ ）。
A ．a ，b ，c ，d B ．d ，c ，b ，a C ．a ，c ，d ，b D ．d ，a ，b ，c 答案（ ） 2．任何一个无向连通图的最小生成树（ ）。
A ．只有一棵 B ．有一棵或多棵 C ．一定有多棵 D ．可能不存在 答案（ ） 3．若待排序列已基本有序，要使它完全有序，从关键字比较次数和移动次数考虑，应当使用的排序方法是（ ）。
A ．归并排序 B ．直接插入排序 C ．直接选择排序 D ．快速排序 答案（ ） 4．有12个节点的平衡二叉树的最大深度是（ ）。
A ．4 B ．5 C ．6 D ．3 答案（ ） 5．对于序列为{12，13，11，18，60，15，7，18，25，100}，用筛选法建堆，必须从值为（ ）的结点开始。
A ．100 B ．12 C ．60 D ．15 答案（ ） 6．在一棵高度为H 的满三叉树中，结点总数为（ ）。
A ．3H - 1 B ．（3H – 1）/2 C ．（3H - 1 ）/3 D ．3H 答案（ ） 7．用二分法在有序表{3，4，10，13，33，42，46，63，76，78，95，96，120}中查找95
时，需要比较次数为（ ）。
A ．2
B ．3
C ．4
D ．5
答案（
）
8
A B.
C
答案（ ）
9．某二叉树的前序遍历结点顺序为：ABCDEFG ，中序遍历结点顺序为：
CBDAFGE ，则后续遍历结点的顺序为：（ ）。
A ．CDBGFEA B.CDGFEA
B C.CDBAGFE D.CDBFAGE
答案（ ）
10．设树T 的度为4，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则T 中叶子结点的个数是（ ）。
A ．5
B ．6
C ．7
D ．8
答案（ ）
二、填空（本大题共10小题，每小题1分，总计10分）
1．无向图中的极大连通子图称为该无向图的 。
2．在堆排序过程中，首先要将待排序的所有键值分放到一棵完全二叉树的各个结点中，然后反复调用“筛选”过程使该完全二叉树具有堆的特性，在建成堆的过程中，需要调用“筛选”过程 次。
3．对50个记录进行折半查找，最多比较次数和最少比较次数分别是 。
4．线性表L={a1，a2，. . . . . . ，a n }用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 。
5．设有一中缀表达式（（E-F ）*G+A/（B-C ））*D ，其等价的后缀表达式是 。
6．设二维数组A[10..20，5..10]按行优先存储，每个元素占4个存储单元，A[10，5]的存储地址为1000，则A[15，10]的存储地址为 。
7．深度为K 的完全二叉树至多和至少分别有 个结点。
8．在计算递归函数时，如不用递归过程，应借助 的数据结构。
9．查找表分为静态查找表和动态查找表两种，二叉排序树属于 。
10．一般树的遍历结果和它所对应的二叉树的遍历结果之间有一定的对应关系：一般树的前序遍历序列和它所对应二叉树的 遍历序列一致，一般树的后序遍历序列和它所对应二叉树的 遍历序列一致。
东北林业大学
2003－2004学年第二学期考试试题
三、解答下列问题（本大题共6小题，每小题5分，总计30分）
1、已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，设每个记录的查找概率相等，用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m。
要求：（1）画出相应的哈希表；
（2）分别求出在等概率情况下，查找成功的平均查找长度；
2、一个空A VL树内，依次插入关键字10，20，30，40，50，60分别画出10，20，30插入完和所有关键字都插入完的A VL树。
3、给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树及其编码。
4、下图是一个地区交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修建公路花费的代价，怎样选择能够沟通每个城市且总造价量省的n-1条公路，画出所有可能的方案。
5、对于给定的一组键值：70，73，69，23，93，18，11，68，分别画出利用快速排序方法对上述序列进行排序中的各趟的结果。
四、算法设计题（本大题共2小题，总计15 分）
1、假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧,编写一个判别表达式中括弧是否正确配对的算法（7分）
2、试编写算法查找二叉链表中数据域值为X的结点（假定各结点数据域值各不相同），并打印出X所有祖先的数据域值。
（8分）
五．（10分）已知二叉树每个非终端节点都有左孩子和右孩子，试回
答下列问题：
（1）若此二叉树有n个叶结点，则此二叉树共有多少个结点？
（2）试证明∑1/2li-1=1
其中n 为二叉树的叶子结点数，li为第i个叶子结点所在的层数。
