淮阴工学院 数据结构期末

一、填空题：（每空1分，共10分） 1. 数据的存储结构种类包括顺序 链接 索引 散列 。 2. 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 以下部分代码的时间复杂度用大O 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示法为       ②        。 int i=1;s=0; while(i<=n) {  s+=i; i=i+2;  } 3. 队列是一种          ③          的特殊的线性表。 4. 线性表的顺序存储结构通常可采用      ④    和      ⑤    两种访问方式。 5. 设一棵完全二叉树有700个结点，则共有      ⑥      个叶子结点。 6. 将一个长度为n的顺序表的第i个元素删除时，只需前移        ⑦              个元素。 7. 设数组a[1…10, 1…20]的起始地址为100，每个元素占4个存储单元，若以行序为主序顺序存储，则元素a[3,5]的存储地址为    　⑧  　  。 8. 排序方法的稳定性是指          ⑨              。 9. 对有序顺序表（3，8，10，25，29，45，55，77，85，99）采用折半查找，若查找表中元素10，它将依次与表中元素              ⑩                    比较大小。 10. 数据的存储结构主要包括                                          。 11. 表达式求值是                应用的一个典型例子。 12. 下面程序段的时间复杂度是                    。 for(j=0; j＜n;j++) a=a+ j； 13. 空串与空格串的区别在于：                        。 14. 单链表表示法的基本思想是用                表示结点间的逻辑关系。 15. 在图1所示的树中，结点G的子孙结点有                    。 16. 在有n个顶点的连通图中，至少有                      条边。 17. 根据二叉树的定义，具有三个结点的二叉树有              种不同的形态，分别是                                        。 18. 排序方法的稳定性是指                                。 19. 设有一稠密图G，则G采用                存储较省空间。 20. 将一个长度为n的顺序表的第i个元素(1≤i≤n)删除时，需向前移动              个元素。 21. 设数组a[1…10, 1…20]的基地址为100，每个元素占4个存储单元，若以列序为主序顺序存储，则元素a[6,16]的存储地址为      　 　  。 22. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是                      。 23. 数据的逻辑结构包括          、            和          三种基本结构。 24. 表达式求值是                应用的一个典型例子。 25. 下面程序段的时间复杂度是                    。 i=1； while(i＜=n) {    t=t+1； i++； } 26. 空串与空格串的区别在于：                        。 27. 单链表的基本思想是用                    表示结点间的逻辑关系。 28. 树的度是指                                                。 29. 交换排序的方法主要包括                                          。 30. 在有n个顶点的简单无向图中，最大可有                      条边。 31. 深度为7（根的层次号为1）的完全二叉树至少有______      _____个结点。 32. 图的存储方式主要有                                                    。 33. 将一个长度为n的线性表的第i个元素(1≤i≤n)删除时，需向前移动              个元素。 34. 设数组a[0…10, 0…20]的基地址为100，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[6,15]的存储地址为      　 　  。 35. 查找表要采用折半查找，必须满足的条件是                                  。 36．称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和_______的数量级相同。 37．在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_________。 38．假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为______。 39．设s=″I AM A ATHLETE″,t=″GOOD″，则执行下列串操作序列之后得到的sub1为________。 substr (sub1,s,5,2)；substr(sub2,s,6,8); strcpy(t1,t); strcat(t1,sub2); strcat(sub1,t1); 40．广义表的深度是指_______。 41．一棵含999个结点的完全二叉树的深度为_______。 42．含n个顶点的无向连通图中至少含有______条边。 43．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为______。 二、选择题： 1. 数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的      和运算的学科。 A.数据                            B. 算法 C.运算                            D. 关系 2. 算法分析的目的是                  。 A. 找出数据结构的合理性          B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进        D. 分析算法的易懂性和文档性 3. 线性表的顺序存储结构是一种                    结构。 A.随机存取                    B.顺序存取        C.索引存取                    D.HASH存取 4. 顺序表和链表均适用于                  查找。 A．随机                      B．二分法      C．顺序，也能二分法          D．顺序 5. 在一个无向图中，顶点的度的和等于边的条数的              倍。 A．1／2          B． l        C． 2            D．4 6. 一组 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 的关键字为{8，2，5，4，7，9}，则利用堆排序的方法建立的初始堆(大顶堆)为        。 A．9，8，7，5，4，2    B．9，7，8，4，2，5 C．9，7，8，4，5，2    D．9，8，7，4，5，2 7. 若在线性表中采用折半查找法查找元素，该线性表应该              。 A．元素按值有序                B．元素按值有序，且采用顺序存储结构 C．采用顺序存储结构            D．元素按值有序，且采用链式存储结构 8. 二叉树是非线性数据结构，所以            。 A. 它不能用顺序存储结构存储;        B. 顺序存储结构和链式存储结构都能存储; C. 它不能用链式存储结构存储;        D. 顺序存储结构和链式存储结构都不能使用 9. 下述几种排序方法中，平均的性能最好的是                  Ａ. 希尔排序      Ｂ. 快速排序        Ｃ. 归并排序      Ｄ. 选择排序 10. 在进行出栈运算时，应先判别栈是否                。 A. 空                B. 满            C. 上溢              D. 下溢 11.一个队列的入队序列是1，2，3，4，则队列的输出序列是            。 A.4，3，2，1                      B.1，2，3，4            C.1，4，3，2                      D.3，2，1，4 12. 一维数组的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是      A.110              B.108            C.100              D.120 13、希尔排序是一种                      排序方法。 Ａ. 插入          Ｂ.选择          Ｃ. 交换            Ｄ. 归并 14、将递归算法转换成对应的非递归算法时，通常需要借助                    结构实现。 A.栈                                B.队列                C.链表                            D.树 15、树最合适用来表示                              。 A.有序数据元素            B. 元素之间无联系的数据 C. 无序数据元素            D. 元素之间具有分支层次关系的数据 16．把一棵树转换为二叉树后，这棵二叉树的形态是          。 A. 唯一的            B. 有多种，但根结点都没有左孩子 C. 有多种            D. 有多种，但根结点都没有右孩子 17．在完全的二叉树中，若一个结点没有                ，则它必定是叶结点。 A．右孩子结点                    B．左孩子结点