数据结构试卷A
页脚内容
6
河南理工大学万方学院 2006-2007学年第
2 学期
《数据结构》试卷（A 卷）
考试方式： 闭卷 本试卷考试分数占学生总评
成绩的 80 %
复查总分 总复查人 一、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，每小题2分，共30分）
1. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1)
(1) O(0) (2) O(1) (3) O(n) (4) O(n 2)
2.在单链表中p 所指结点后插入s 所指结点,则下列语句正确的是( )
(1) p →next=s; s →next=p; (2) s →next=p →next; p →next=s;
(3) s →next=p; p →next=s; (4) p →next=s →next; s →next=p;
3. 设一个栈的输入序列为A ，B ，C ，D ，则借助一个栈所得到的输出序列不可能是( )
（1）A ，B ，C ，D （2）D ，C ，B ，A （3）A ，C ，D ，B （4）D ，A ，B ，C
4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ）
（1） 根结点无右子树的二叉树 （2） 根结点无左子树的二叉树
（3） 根结点可能有左二叉树和右二叉树 （4） 根结
总 分 题号 一 二 三 四 核分人
得分
得分 评卷人
毋小省
……
点只有一个孩子结点的二叉树
5．设二叉树的根为第一层，则深度为i的二叉树结点数最多为（）
（1）２i（2）２i+1 （3）２i-１（4）２i -1
6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为()
（1）前序遍历（2）后序遍历（3）中序遍历（4）
层次遍历
7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（）
（1）12534 （2）12435 （3） 14325 （4）12345
8．散列表中的冲突是指（）
（1）两个元素具有相同的序号（2）两个元素的
关键字相同，而其他属性相同
（3）不同的关键字对应相同的存储地址（4）数据元素
的地址相同
9. 线性表若采用链式存储结构时，要求内存中可用存储单
元的地址:（）
（1）必须是连续的（2）部分地址必须是连续的
（3）一定是不连续的（4）连续或不连续都可以
10．下面程序段的时间复杂度为（）
for (int i=1;i for (int j=1;j a[i][j]=i*j; (1) O(m2) (2) O(n2) (3) O(m*n) (4) O(m+n) 11．当利用大小位的数组顺序存储一个队列时，该队列的最大长度为（） （1）n-2 (2) n-1 (3) n (4)n+1 12．对线性表进行折半搜索时，要求线性表必须（） （1）顺序存储（2）顺序存储且结点按关键字有序 （3）链式存储（4）链式存储且结点按关键字有序 13．采用线性探查法解决冲突时所产生的一系列后续地址（） （1）必须大于等于原散列地址（2）必须小于等于原散列地址 （3）可以大于或小于但不等于原散列地址（4）对地址在何处没有限制 14．栈的插入和删除操作在（）进行。 页脚内容6 （1）栈顶（2）栈底（3）任意位置（4）指定位置 15．在一个顺序存储的循环队列中，对头指针指向队列的（）位置。 （1）前一个（2）后一个（3）当前（4）后面 二、填空题（每空1分，共20分） 1.数据的逻辑结构被分为___0__________，________________，_________________，________________。 2.单链表 与循环链表的区别是 _______________________________。 3.在一个循环队列中，判断对空的条件是串是____________________，判断对满的条件是串是_______________________________ 4. 从有序表（12，18，30，43，56，78，82，95）中一次折半搜索43和56元素是，其比较次数分别为_______和_______。 5.与哈西表的平均查找长度有关的三个因素分别是_____________________________，____________________ ，_____________________。 6.对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数个边数分别为_________和__________。 7.在二叉排序树中，左子树所有结点的关键字值都________ 该结点的关键码值，而右子树中所有结点的关键字值都 _________该结点的关键码值。 8.在一个小顶堆中，堆顶元素的值是所有结点中的 ______________，在一个大顶堆中，堆顶元素的值是所有结点 中的______________。 9.假定一组纪录的关键字为（46，79，56，38，40，80），对 其进行快速排序的一次划分的结果为 __________________________________。 10.在一个网络的所有生成树中，各边权值之和最小的生成 树，称为该网络的______________。 三、判断题（判断下列各题是否正确， 若正确在（）内打“√”，否则“×”。每小 题1分，共10分） （）1. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）2. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （）3.二叉树中任何一个结点的度都是2。 （）4.有回路的有向图不能完成拓扑排序。 （）5.按先根次序遍历森林等同于按先序法遍历对应的二 页脚内容6 叉树。 （）6.n（n>1）个顶点的无向连通图最少由n-1条边。 （）7.有向图的邻接表表示中边表中结点的总数与有向图中有向边的条数相等。 （）8.一个无向图的邻接矩阵中各元素之和与图中边的条数相等。 （）9.归并排序要求待排序文件已部分排序。 （）10.顺序检索时数据的存储方式可以是顺序的，也可以是链接的。 四、综合题（共40分） 1．已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。 (7分) 2．设待排序的记录的关键字序列为{12，2，16，30，10，20，18}，写出使用链式基数排序每趟的结果。(6分) 3、拓扑排序的结果不是唯一的，对于下图的结点进 行拓扑排序，试写出其中的任意5个。 (5分) V V V 页脚内容6 4．分别按前序、后序、对称序列写出下图二叉树的结点，并转化为树林，分别按先根次序、后根次序列出其结点。(6分) 5.已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H(key)=key MOD 13,表长为13，分别用线性探查法和链地址法处理冲突构造哈希表，并计算各平均查找长度。(10分) 6.程序填空(6分) 对有序表R[0]至R[n-1]进行二分查找，成功时返回记录在表中的位置，失败时返回0. Struct sqlist { keytype key; }; int binsrch(sqlist R[ ],keytype k) //在表R中查找关键字k { int low ,high,mid; I 页脚内容6 low=0; high=n-1; while( ) mid=(low+high)/2; if (k==R[mid].key) return mid; else if( k ; else ; } return 0; } 页脚内容6 河南理工大学万方学院 2006-2007学年第 2 学期 《数据结构》试卷（A卷） 考试方式：闭卷本试卷考试分数占学生总评成绩的80 % 复查总分总复查人 一、单选题（本题的每一备选答案中， 只有一个是正确的，请把你认为正确的答案 的题号填入题干的括号内，每小题2分，共 30分） 1. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1) (1) O(0) (2) O(1) (3) O(n) (4) O(n2) 2.在单链表中p所指结点后插入s所指结点,则下列语句正确的是( ) (1) p→next=s; s→next=p; (2) s→next=p→next; p→next=s; (3) s→next=p; p→next=s; (4) p→next=s→next; s→next=p; 3. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是( ) （1）A，B，C，D （2）D，C，B，A （3）A，C，D，B （4）D，A，B，C 4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（） （1）根结点无右子树的二叉树（2）根结点无左子树的二叉树 （3）根结点可能有左二叉树和右二叉树（4）根结点只有一个孩子结点的二叉树 5．设二叉树的根为第一层，则深度为i的二叉树结点数最多为（） （1）２i（2）２i+1 （3）２i-１（4）２i -1 6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为() （1）前序遍历（2）后序遍历（3）中序遍历（4）层次遍历 7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（） （1）12534 （2）12435 （3）14325 （4）12345 8．散列表中的冲突是指（） （1）两个元素具有相同的序号（2）两个元素的关键字相同，而其他属性相同 （3）不同的关键字对应相同的存储地址（4）数据元素的地址相同 9. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（） （1）必须是连续的（2）部分地址必须是连续的 （3）一定是不连续的（4）连续或不连续都可以 10．下面程序段的时间复杂度为（） for (int i=1;i 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 《数据结构》试卷 选择题（从下列答案选项中选出一个正确答案，每小题2分，共22分) 1.在数据结构中，与所使用的计算机无关的是数据的（）结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 2.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存 储方式节省时间。 A.单链表 B.双链表 C.顺序表 D.单循环链表 3.已知模式串t=“abcaabbcabcaabdab”，该模式串的next数组值为（）。 A.-1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1 B.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 C.-1，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 D.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1， 4.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个 元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 5.一棵含有101个结点的完全二叉树存储在数组bt[102]中，其中bt[0]不用，若bt[k] 是叶子结点，则k的最小值是（）。 A.51 B.50 C.49 D.48 6.稀疏矩阵一般的压缩存储方法有两种，即（）。 A.二维数组和三维数组 B.三元组表和散列表 C.三元组表和十字链表 D.散列表和十字链表 7.对顺序存储的18个数据元素（A[1]~A[18]）的有序表做二分查找，则查找A[3]的 比较序列的下标为( )。 A.1，2，3 B.9，5，2，3 C.9，5，3 D.9，4，2，3 8.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与 图中的结点的个数有关，而与图的边数无关，这种说法（）。 A.正确 B.错误 9.下列排序算法中，某一趟排序结束后未必能选出一个元素放在最终位置上的是（ ）。 A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序 10.在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已 知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（）型 调整使其平衡。 A.LL B.LR C.RL D.RR 11.在解决计算机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机 将要输出的数据依次写入该缓冲区，而打印机依此从该缓冲区中取出数据打印，该 缓冲区应是一个（）结构。 A.堆栈 B.队列 C.顺序表 D.链表 二、填空题（每空2分，共18分） 1.以下程序段的时间复杂度是________________________，其中n为正整数。 int i=1; while(i<=n) i=i*2; 2.对顺序存储结构的线性表，设表长为n；在等概率假设条件下，插入一个数据元素 需平均移动表中元素______________个；在最坏情况下需移动表中元素 ______________个。 3.设树T的度为4，其中度为1、2、3、4的结点的个数分别为4、3、2、1，则树T 的叶子结点的个数是。 4.判定一个环形队列qu（最多元素为MaxSize）为空的条件是 __________________________________________，判定环形队列qu为满队列的条 北京师范大学2011～2012学年第 1 学期期末考试试卷（A 卷） 课程名称： 数据结构 任课教师姓名： 刘玉铭 卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）： 数学科学学院 专 业： 年级： 2010 姓 名： 学 号： 阅卷教师（签字）： 一、 单项选择题（每题2分，共10题20分） 1．以下那一个术语与数据的存储结构无关？ 。 A ．栈 B ．哈希表 C ．线索树 D ．双向链表 2．链表不具有的特点是 。 A ．插入、删除不需要移动元素 B ．可随机访问任一元素 C ．不必事先估计存储空间 D ．所需空间与线性表长度成正比 3．算术表达式a+b*（c+d/e ）转为后缀表达式后为 。 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．abcde*/++ 4．二维数组A[10][20]采用列优先的存储方法,若每个元素占2个存储单元，设A[0][0]的地址为100，则元素A[7][6]的存储地址为 。 A ．232 B ．234 C ．390 D ．392 装 订 线 5．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是。 A．9 B．11 C．15 D．不确定 6．一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB 7．在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是。 A．G 中有弧 读书破万卷下笔如有神 《数据结构》试卷（A卷） 一、选择题 1. 数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 D.顺序存储结构 C. 链式存储结构 3. 树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 D. 一对多关系 C.多对一关系 4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; 23nn) D.O(C.O(n) B.O( ) A.O(1) 5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 不好说D. 相同C. 高B. 低A. 读书破万卷下笔如有神 8. 数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（）。 A.数据 B.数据元素 C.数据项 D.数据库 11.若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。 -精品- 河南理工大学万方学院 2006-2007学年第 2 学期 《数据结构》试卷（A 卷） 考试方式： 闭卷 本试卷考试分数占学 生总评成绩的 80 % 复查总分 总复查人 一、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，每小题2分，共30分） 1. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1) (1) O(0) (2) O(1) (3) O(n) (4) O(n 2) 2.在单链表中p 所指结点后插入s 所指结点,则下列语句正确的是( ) (1) p →next=s; s →next=p; (2) s →next=p →next; p →next=s; (3) s →next=p; p →next=s; (4) p →next=s →next; s →next=p; 3. 设一个栈的输入序列为A ，B ，C ，D ，则借助一个栈所得到的输出序列不可能是( ) （1）A ，B ，C ，D （2）D ，C ，B ，A （3）A ，C ，D ，B （4）D ，A ，B ，C 4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ） （1） 根结点无右子树的二叉树 （2） 根结点无左子树的二叉树 （3） 根结点可能有左二叉树和右二叉树 （4） 根结点只有一个孩子结点的二叉树 5．设二叉树的根为第一层，则深度为i 的二叉树结点数最多为（ ） （1）２i （2） ２i +1 （3）２i -１ （4）２i -1 6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( ) （1）前序遍历（2）后序遍历（3）中序遍历（4）层次遍历 7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（）（1）12534 （2）12435 （3）14325 （4）12345 8．散列表中的冲突是指（） （1）两个元素具有相同的序号（2）两个元素的关键字相同，而其他属性相同 （3）不同的关键字对应相同的存储地址（4）数据元素的地址相同 9. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（） （1）必须是连续的（2）部分地址必须是连续的 （3）一定是不连续的（4）连续或不连续都可以 10．下面程序段的时间复杂度为（） for (int i=1;i 《数据结构》试卷 第3 页（共3 页） 河南理工大学万方学院 2006-2007学年第 2 学期 《数据结构》试卷（A 卷） 考试方式： 闭卷 本试卷考试分数占学 生总评成绩的 80 % 复查总分 总复查人 一、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，每小题2分，共30分） 1. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1) (1) O(0) (2) O(1) (3) O(n) (4) O(n 2 ) 2.在单链表中p 所指结点后插入s 所指结点,则下列语句正确的是( ) (1) p →next=s; s →next=p; (2) s →next=p →next; p →next=s; (3) s →next=p; p →next=s; (4) p →next=s →next; s →next=p; 3. 设一个栈的输入序列为A ，B ，C ，D ，则借助一个栈所得到的输出序列不可能是( ) （1）A ，B ，C ，D （2）D ，C ，B ，A （3）A ，C ，D ，B （4）D ，A ，B ，C 4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ） （1） 根结点无右子树的二叉树 （2） 根结点无左子树的二叉树 （3） 根结点可能有左二叉树和右二叉树 （4） 根结 点只有一个孩子结点的二叉树 5．设二叉树的根为第一层，则深度为i 的二叉树结点数最多为（ ） （1）２i （2） ２ i +1 （3）２ i -１ （4）２i -1 6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( ) （1）前序遍历（2）后序遍历（3）中序遍历（4）层次遍历 7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（）（1）12534 （2）12435 （3） 14325 （4）12345 8．散列表中的冲突是指（） （1）两个元素具有相同的序号（2）两个元素的关键字相同，而其他属性相同 （3）不同的关键字对应相同的存储地址（4）数据元素的地址相同 9. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（） （1）必须是连续的（2）部分地址必须是连续的（3）一定是不连续的（4）连续或不连续都可以 10．下面程序段的时间复杂度为（） for (int i=1;i 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 选择题（查找排序不考） 1．下面关于线性表的叙述错误的是（D ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B ）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 3．设顺序循环队列Q[0：M-1]的头 指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5．设某完全无向图中有n个顶点，则该完全无向图中有（A ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2(D) n2-1 6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（B）个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ C ）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8 1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（B）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构 2．下面程序的时间复杂为（B ） for（i=1，s=0；i<=n；i++） { t=1； for(j=1；j<=i；j++) t=t*j； s=s+t； } (A) O(n) (B) O(n2) (C) O(n3) (D) O(n4) 3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A ）。 一、判断题（正确在括号内填√，错误在括号内填×，每题1分，共 15分） （）1．线性表采用顺序存储，必须占用一片连续的存储单元。 （）2．栈和队列的共同点是只允许在端点处插入和删除元。 （）3．数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。。（）4．一棵哈夫曼树中不存在度为1的结点。 （）5．散列法是一种对关键字进行运算的查找方法和存储方法。 （）6．一个队列的入队序列是1,2,3,4,则队列的出队序列是4,3,2,1。 （）7．数据元素是数据的最小单位。 （）8．算法的五个特性为：有穷性、输入、输出、完成性和确定性 （）9．线性表采用链式存储结构时，其地址必须是连续的。 （）10．二叉树中任何一个结点的度都是2。 （）11．直接插入排序是稳定的排序。 （）12．n个顶点的无向图最多有n*(n-1)条边。 （）13．一个有向图的邻接矩阵一定是一个非对称矩阵。 （）14．用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。 （）15．设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为2h-1。 二、单项选择（在备选答案中选出一个正确答案，并将正确答案 的序号填在题干后的括号内。每题1分，共15分） 1. 下列算法的时间复杂度为（）。 x=n;// n>1 While(x>=(y+1)*(y+1)) Y++; A．O(n1/2) B．O(n2) C． O(log2n) D．O(n) 2. n个顶点的无向连通图的最小生成树包含( )条边。 A.n B.n-1 C.n/2 D.n+1。 3. 深度为6（根的层次为1）的二叉树最多有（）个结点。 A．64 B．32 C． 63 D．31 4. 一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素 的地址是( ) 。 A. 110 B. 120 C. 100 D. 108 5. 在一个单链表中，若删除p所指结点的后续结点，则执行（） A．p->next=p->next->next ; B．p=p->next; C．p->next=p->next; D．p =p->next->next; 6 . 稀疏矩阵一般的压缩存储方法有两种,即（）。 A．二维数组和三维数组 B．三元组和十字链表 C．散列和十字链表 D．三元组和散列 7. 按照二叉树的定义,具有3个结点的二叉树有（）种。 A．3 B．4 C．5 D．6 8. 具有4个顶点的无向完全图有（）条边。 A. 6 B. 20 C. 16 D. 12 9. 经过以下栈运算后，x的值是。 InitStack(s); Push(s, a); Push(s, b); Pop(s, x) ; GetTop(s, x); A. a B. b C. 1 D. 0 10. 在一个长度为N的顺序表中，删除第i个元素，需向前移动元素的个数（）。 A.N-i-1 B. N-i C. N-i+1 D.i 11. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队满的条件是（）。 A. rear+1=front B. rear=front C．(rear+1) MOD n=front D. (rear-l) MOD n=front 12. 具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。 A. 6 B. 7 C. 8 D. 5 13. 采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为（） Ａ . (n+1)/2 Ｂ. n/2 Ｃ. n Ｄ. (n-1)/2 14. 无向图的邻接矩阵是一个（）。 A. 零矩阵 B. 对称矩阵 C. 上三角矩阵 D. 对角矩阵 15. 有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当用二分 查找法查找键值为4的结点时，经（）比较后查找成功。 A. 2 B. 4 C. 3 D. 12 三、简答与应用题（第1题5分，2—6每题7分，共40分） 1. 画出5种不同型态的二叉树。 2. 对于给定的5个实数W={8，5，13，2，7}，试构造Huffman树，并求出该树的最小带权 路径长度WPL。 3. 对下面的数据序列，写出采用冒泡排序算法排序的每一趟排序的结果。 （50，72，31，80，60，20，96，14） 4. 设散列表长度为11，散列函数H（K）=K%11，采用线性探测法处理冲突，若输入序列为 （100，90，120，60，78，35，42，31，15，88），要求构造出散列表。 2011?2012学年第1学期期末考试试卷（A卷） 课程名称：数据结构 ____________ 任课教师姓名：______________ 卷面总分：100 分考试时长：100 分钟考试类别：闭卷 院（系）：_________________ 专业：_______________________________ 年级：2010 阅卷教师（签字）：________________________ 单项选择题（每题2分，共10题20 分） 1. ________________________________________________ 以下那一个术语与数据的存储结构无关？________________________________________ A. 栈 C .线索树 B .哈希表 D .双向链表 2. ________________________________________ 链表不具有的特点是。 A. 插入、删除不需要移动元素C?不必事先估计存储空间 B. 可随机访问任一元素D.所需空间与线性表长度成正比 3. ________________________________________________________ 算术表达式 a+b* （c+d/e）转为后缀表达式后为______________________________ 。 A . ab+cde/* C. abcde/*++ B. abcde/+*+ D. abcde*/++ 4. 二维数组A[10][20]采用列优先的存储方法，若每个元素占2个存储单元，设A[0][0] 的地址为100,则元素A[7][6]的存储地址为____________________ 。 A. 232 B. 234 C. 390 D . 392 好风光好感动1、线性表的逻辑顺序与物理顺序总是一致的。( x ) 2、线性表的顺序存储表示优于链式存储表示。( X ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( v ) 4、二维数组是其数组元素为线性表的线性表。( v ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( x ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( v ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（x ） 8、线性的数据结构可以顺序存储，也可以存储。非线性的数据结构只能存储。（x ） 9、栈和队列逻辑上都是线性表。（v ） 10、单链表从任何一个结点出发，都能访问到所有结点（v ） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（x ） 12、快速排序是排序算法中最快的一种。（x ） 13、多维数组是向量的推广。（x） 14、一般树和二叉树的结点数目都可以为0。（v） 15、直接选择排序是一种不稳定的排序方法。（x ） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（v ） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（x ） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（x ） 19、堆栈在数据中的存储原则是先进先出。（x ） 20、队列在数据中的存储原则是后进先出。（x ） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（x ） 22、哈夫曼树一定是满二叉树。（x ） 23、程序是用计算机语言表述的算法。（v） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（v ） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（v ） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（v ） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（x ） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（v ） 29、希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。（v ） 数据结构试卷（一） 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 ___________。 11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序 过程的时间复杂度为________。 12.在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、计算题（每题6 分，共24分） 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2.请画出下图的邻接矩阵和邻接表。 3.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 四、阅读算法（每题7分，共14分） 1.LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1：while(p－>next) p=p－>next； 《数据结构》自考复习思考试题○10 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上 ( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为( ) A. m B. n-m C. n-m+1 D. n 8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为( ) A. 429 B. 432 . 2010年《数据结构》期终考试试卷（A） 班级学号姓名 一、简答题（每小题6分，共30分） (1) 假设一个线性链表的类名为linkedList，链表结点的类名为ListNode，它包含两个数据成员data和link。data存储该结点的数据，link是链接指针。下面给定一段递归打印一个链表中所有结点中数据的算法： void PrintList (ListNode *L) { if ( L != NULL ) { cout << L->data << endl; PrintList ( L->link ); } } 试问此程序在什么情况下不实用？给出具体修改后的可实用的程序？ (1) 此程序在内存容量不足时不适用。因为需要一个递归工作栈。当链表越长，递归工作栈的深度越深，需要的存储越多。可采用非递归算法节省存储。 void PrintList (ListNode *L) { while ( L != NULL ) { cout << L->data << endl; L = L->link; } } (2) 如果每个结点占用2个磁盘块因而需要2次磁盘访问才能实现读写，那么在一棵有n个关键码的2m阶B树中，每次搜索需要的最大磁盘访问次数 是多少？ (2) 在2m阶B树中关键码个数n与B树高度h之间的关系为h≤log m ((n+1)/2)+1，那么每次搜索最大磁盘访问次数为2h max = 2log m ((n+1)/2)+2。 (3) 给定一棵保存有n 个关键码的m 阶B 树。从某一非叶结点中删除一个关键码需要的最大磁盘访问次数是多少？ (3) 在m 阶B 树中关键码个数n 与B 树最大高度h 的关系为h = log m/2((n+1)/2)+1。若设寻找被删关键码所在非叶结点读盘次数为h ’，被删关键码是结点中的k i ，则从该结点的p i 出发沿最左链到叶结点的读盘次数为h -h ’。当把问题转化为删除叶结点的k 0时，可能会引起结点的调整或合并。极端情况是从叶结点到根结点的路径上所有结点都要调整，除根结点外每一层读入1个兄弟结点，写出2个结点，根结点写出1个结点，假设内存有足够空间，搜索时读入的盘块仍然保存在内存，则结点调整时共读写盘3(h -1)+1。总共的磁盘访问次数为 h ’+(h -h ’)+3(h -1)+1 = 4h - 2 = 4(log m/2 ((n+1)/2)+1)-2 = = 4log m/2 ((n+1)/2)+2 (4) 给定一个有n 个数据元素的序列，各元素的值随机分布。若要将该序列的数据调整成为一个堆，那么需要执行的数据比较次数最多是多少？ (4) 设堆的高度为h = log 2(n+1)，当每次调用siftDown 算法时都要从 子树的根结点调整到叶结点，假设某子树的根在第i 层（1≤i ≤h -1），第h 层的叶结点不参加比较。从子树根结点到叶结点需要比较h -i 层，每层需要2次比较：横向在两个子女里选一个，再纵向做父子结点的比较。因此，在堆中总的比较次数为 )i h j ( 2j 2 2j 22 2j 2 2)i h (221 h 1 j j 1 -h 1 h 1 j j -1 h 1 h 1 j 1 -j -h 1 h 1 i 1-i -=??=??=?=-∑ ∑∑∑-=-=--=-=代换 因为 2h-1 ≤n ≤2h -1，且∑-=∞ →=1 h 1j j h 22j lim ，则n 42n 22 j 221 h 1j j 1 h =??≤??∑-=-数据结构试卷A
2017年数据结构期末考试题及答案A
数据结构A卷试题及答案
数据结构试卷-A+答案
数据结构试卷A卷
数据结构试卷A
数据结构试卷A
数据结构试题及答案
数据结构试题及答案
数据结构试卷及答案
数据结构试卷A(信息管理专业)
2数据结构试卷a答案
数据结构试题及答案
十套数据结构试题及答案
(完整版)数据结构试题及答案
数据结构期终考试试卷A清华大学
- 数据结构试卷(A)答案
- 2022年西安工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
- 2022年西安工程大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
- 数据结构试题A
- 数据结构(A卷)【含答案】
- 2022年安徽理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
- 2022年湖南农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
- 数据结构期末考试试卷A
- 2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
- 《数据结构与算法分析》期末试卷A(答案)
- 122-《数据结构》试卷A参考答案
- 数据结构试卷
- 2022年泰山学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
- 数据结构试题A
- 数据结构与算法A卷答案
- 2022年成都大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
- 数据结构试题及答案
- 数据结构试卷A卷(含答案)
- 十套数据结构试题及答案
- 数据结构试题A