《郑州大学远程教育学院数据结构试题及答案.doc》由会员分享，可在线阅读，更多相关《郑州大学远程教育学院数据结构试题及答案.doc（30页珍藏版）》请在金锄头文库上搜索。
1、 郑州大学现代远程教育数据结构课程（本科）学习指导书郭纯一 编n 课程内容与基本要求“数据结构”在计算机科学中是一门综合性的专业基础课。本课程将主要介绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈和队列、串、树和图）和基本技术（查找和排序方法）三大部分。本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数据合理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法；还应初步掌握算法的时间和空间效率的分析方法。n 课程学习进度与指导章节课程内容学时分配学习指导（均以课件学习为主）第一章绪论4学时
2、重点掌握基本概念和时间复杂度的计算方法第二章*线性表10学时重点掌握顺序结构和链式结构表示线性表的方法和操作的实现；结合具体例子理解编程实现一个问题的2种方法第三章栈和队列8学时重点掌握栈和队列的特点以及它们各自的存储表示，尤其是顺序栈和循环队列的实现；结合具体例子理解栈和队列的应用第四章串2学时重点掌握串的术语、串操作结果和不同存储结构的特点第七章*树和二叉树10学时重点掌握二叉树的定义、存储、性质、遍历算法（递归）及应用、线索化；掌握树和森林与二叉树的转换以及Huffman树和Huffman编码的构造方法第八章图8学时重点掌握图的术语、存储、遍历算法及应用；掌握最小生成树的2种构造方法及特
3、点、会求拓扑排序序列和单源最短路径第九章*查找8学时重点掌握各种动态查找表的构造过程、性能分析、插入/删除方法；掌握静态查找表的顺序、折半和分块查找及ASL求法第十章*排序8学时掌握关于排序的术语及分类方法；重点掌握插入排序、交换排序、选择排序等内排序方法及其性能分析方法第一章 绪论一、 章节学习目标与要求1、 理解数据抽象和信息隐蔽原则 2、 掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型和算法；能够熟练使用C语言编写程序二、 本章重点、难点重点：基本概念和术语，C语言描述算法的方式，简单程序的时间复杂度的求法。 难点：时间复杂度的计算方法和原则。三、 章节练
4、习（一）选择题：1 具有线性结构的数据结构是_。A.图 B. 树 C. 集合 D. 栈2 计算机算法是指_。A.计算方法和运算结果 B.调度方法 C. 解决某一问题的有限运算系列 D. 排序方法3 线性结构中，最后一个结点有_个后继结点。 A. 0 B. 1 C. 任意多4. 算法分析的目的是_。A. 找出数据结构的合理性 B. 研究算法中输入和输出的关系 C. 分析算法的效率以求改进 D.分析算法的可读性和可行性5. 具有非线性结构的数据结构是_。A.图 B. 线性表 C. 串 D. 栈6算法具有5个特性：_、_、_、输入和输出。A. 稳定性、确定性、可行性 B. 有穷性、确定性、可行性C.
5、 有穷性、安全性、可行性 D. 有穷性、确定性、可移植性7设n为正整数。则下面程序段的时间复杂度为_。i=1; k=0; while(i=n-1) k+=10*i; i+; A.O(1) B. O(n) C. O(nlogn) D. O(n2)8设n为正整数。则下面程序段的时间复杂度为_。k=0; for(i=1;i=n;i+) for(j=i;jnext=NULL; B. p=NULL; C. p-next=head; D. p=head;4若在线性表的任何位置上插入元素的概率是相等的，那么在长度为n的顺序表中插入一个元素时需平均移动_个元素。A. n B. (n-1)/2 C.n/2 D.
6、 (n+1)/25在带头结点的非空单链表中，头结点的位置由_指示，首元结点的存储位置由_指示，除首元结点外，其它任一元素结点的存储位置由_指示。A. 头指针 B. 头结点的指针域的指针 C.前驱结点的指针域的指针6. 单链表的头指针为p，若有头结点，则表空的判断条件是_；若不带头结点，则表空的判断条件是_。A. p=NULL B. p-next=NULL C. p-next-next=NULL（二）判断题：1在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素。 （ ）2 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。 （ ）3.
7、 在不带头结点的非空单链表中，首元结点的存储位置由头指针指示，除首元结点外，其它任一元素结点的存储位置由前驱结点的指针域的指针指示。 （ ）（三）问答题：1若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）？为什么？2若线性表经常做插入/删除操作，则应采取什么存储结构？为什么？3. 在单链表中设置头结点有什么作用？（四）算法题：1.设带头结点的单链表(L为头指针)中的数据元素递增有序。设计算法，将x插入到链表的适当位置上，并仍保持该表的有序性。2.设顺序表va中的数据元素递增有序。设计算法，将x插入到顺序表的适当位置上，并仍保持该表的有序性。3.设计算法，实
8、现单链表的就地逆置，即利用原表的存储空间将线性表（a1,a2,an）逆置为（an ,an-1,a1）。第三章 栈和队列一、 章节学习目标与要求1、理解用栈和队列解决实际问题的方法。2、掌握栈和队列的定义以及特性、它们的2种不同的存储表示方法（特别是顺序栈和循环队列）以及各种常见操作（如入、出操作）在不同表示方式上的实现。二、本章重点、难点重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解 难点：循环队列的表示及为解决循环队列队空、队满判断条件相同而使用的不同实现方式；能在具体问题中灵活运用栈和队列结构。三、章节练习（一）选择题：1一个栈的入栈序列是a,b,c,d,e,则栈的不可能的
9、输出序列是_。A. edcba B.decba C.dceab D.abcde2栈和队列的共同点是_。 A. 都是后进先出 B. 都是先进先出 C. 都是只允许在端点处插入和删除元素 D.无共同点3一个队列的入队序列是1,2,3,4,则队列的输出序列是_。 A. 4321 B. 1234 C. 1432 D. 32414栈的入栈序列是1，2，n，输出序列为p1,p2,pn,若p1=n, 则pi为_。A. i B. n-i C. n-i+1 D. 不确定5队列是限定在_进行插入，在_进行删除的线性表。A. 队头 B. 队尾 C. 任意位置6循环队列中，设队列元素依次存放在Q0.m中，f、r分别指
10、示队头元素位置和队尾元素的下一个位置，约定存储m个元素时为队满。则队列空的判定方法是_,队列满的判定方法是_。A.f=r B. (f+1)%(m+1)=r C. (r+1)%(m+1)=f D. (r+1)% m=f（二）判断题：1若用户无法估计所用队列的最大长度，则最好采用链队列。 （ ）2在链队列上删除队头元素时，只需修改头结点中的指针，不必修改尾指针。 （ ）3. 栈是限定仅在栈顶进行插入或删除操作的线性表。 （ ）4. 队列是限定在队尾插入元素，在队头删除元素的线性表。 （ ）（三）问答与算法题：1对于一个栈，若输入序列依次为A,B,C, 试给出所有可能的输出序列。2假设将循环队列定义
11、为：以整型域变量front和length分别指示循环队列中队头元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的入队列和出队列的算法。第四章 串一、 章节学习目标与要求1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。二、本章重点、难点重点：串的基本运算、串的各种存储表示和特点。继续加深对线性结构的理解 难点：串的不同存储结构，区分它们和高级语言中串的存储方式的不同。三、章节练习（一）选择题：1设串s=I AM A STUDENT, 则其串长是_。 A. 13 B. 14 C. 15 D. 162. 设s =HE IS A WORKER,t=WORKER。则StrIndex
