《2019年西南大学春季[0012]《数据结构》辅导答案》由会员分享，可在线阅读，更多相关《2019年西南大学春季[0012]《数据结构》辅导答案（16页珍藏版）》请在金锄头文库上搜索。
1、1、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ）1. A. 选择排序2. 希尔排序3. 快速排序4. 归并排序2、不定长文件是指（ ）1. 记录的长度不固定2. 关键字项的长度不固定3. 字段的长度不固定4. 文件的长度不固定 3、如下陈述中正确的是（ ）1. 串中元素只能是字母 2. 串是一种特殊的线性表3. 串的长度必须大于零4. 空
2、串就是空白串4、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）1. O（m+n）2. O（n）3. O（m）4. O（1） 5、设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）1. F. front=(front+1)%m2. front=(front-1)%m3. front=front+14. front=(front+1)%(m-1)6、计算机算法必须具备输入、输出和等5个特性1. 易读性、稳定性和安全性2. 确定性、有穷性和稳定性3. 可行性、可移植性和可扩充性4. 可行性、确定性
3、和有穷性7、有8个结点的无向图最多有条边1. 1122. 563. 284. 148、不含任何结点的空树1. 是一棵树2. 是一棵二叉树3. 是一棵树也是一棵二叉树4. 既不是树也不是二叉树9、一棵深度为6的满二叉树有个分支结点1. 302. 313. 324. 3310、把一棵树转换为二叉树后，这棵二叉树的形态是1. 唯一的2. 有多种3. 有多种，但根结点都没有左孩子4. 有多种，但根结点都没有右孩子11、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是:1. O(log2n)2. O(1)3. O(n)4. O(nlog2n)12、若需要在O(nlog2n)的时间内完成对数组的
4、排序，且要求排序是稳定的，则可选择的排序方法是（ ）1. 快速排序2. 堆排序3. 归并排序4. 直接插入13、设哈希表长m=14,哈希函数H(key)=key MOD 11。表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为:1. 32. 53. 84. 914、设一棵完全二叉树有300个结点，则共有个叶子结点1. 1502. 1523. 1544. 15615、由个结点所构成的二叉树有 种形态.1. 22. 33. 44. 516、设有两个串p和q，求q在p中首次出现的位
5、置的运算称作：1. 连接2. 模式匹配3. 求子串4. 求串长17、栈中元素的进出原则是:1. 先进先出2. 后进先出3. 栈空则进4. 栈满则出18、链表是一种采用存储结构存储的线性表.1. 顺序2. 星式3. 链式4. 网状19、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：1. 存储结构2. 顺序存储结构3. 逻辑结构4. 链式存储20、判断一个循环队列Q（最多n个元素）为满的条件是:1. Q-front=(Q-rear+1)%n2. Q-rear=Q-front+13. Q-front=(Q-rear-1)%n4. Q-rear=Q-front21、在单链表中
6、，指针p指向元素为x的结点，实现删除x的后继的语句是:1. p=p-next2. p=p-next-next3. p-next=p4. p-next=p-next-next22、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是:1. p-next=q;q-prior=p;p-next-prior=q;q-next=q;2. q-prior=p;q-next=p-next;p-next-prior=q;p-next=q;3. q-next=p-next;q-prior=p;p-next=q;p-next=q;4. p-next=q;p-next-prior=q
7、;q-prior=p;q-next=p-next;23、在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )1. C. 72. 63. 44. 5 24、算法指的是（ ）1. B. 排序算法2. E. 解决问题的计算方法3. 计算机程序4. 解决问题的有限运算序列25、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )1. n*n2e2. e3. n*ne4. 2e26、线性表采用链式存储时，结点的存储地址（ ）1. D. 连续与否均可2. 必须是连续的3. 和头结点的存储地址相连续4. 必须是不连续的多项选择题27、抽象数据类型的组成部分分
8、别为:1. 数据对象2. 存储结构3. 数据关系4. 基本操作28、不具有线性结构的数据结构是：1. 图2. 栈3. 广义表4. 树29、算法分析的两个主要方面是( )1. 正确性2. 简单性3. 空间复杂度4. 时间复杂度判断题30、树在实际应用中采用多种不同的形式表示和存储1. A.2. B.31、完全二叉树一定是满二叉树1. A.2. B.32、在完全二叉树中，叶节点个数比分支节点个数多11. A.2. B.33、任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。1. A.2. B.34、栈和队列逻辑上都是线性表1. A.2. B.35、算法分析的两个主要方面是时间复杂度和空间复
9、杂度的分析。1. A.2. B.36、若用链表来表示一个线性表，则表中元素的地址一定是连续的。1. A.2. B.37、链表的每个结点中都恰好包含一个指针1. A.2. B.38、如果将所有中国人按照生日来排序，则使用哈希排序算法最快1. A.2. B.39、折半查找只适用于有序表，包括有序的顺序表和链表1. A.2. B.40、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。1. A.2. B.41、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。1. A.2. B.42、一般树和二叉树的结点数都可以为0;1. A.2. B.43、通
10、过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：1231. A.2. B.44、不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑溢出情况。1. A.2. B.45、一棵有124个结点的完全二叉树，其叶结点个数是确定的1. A.2. B.主观题46、中序遍历二叉排序树所得到的序列是_序列（填有序或无序）。参考答案：有序 47、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间.参考答案：顺序表 48、设某无向图中顶点数和边数分别为n和e，所有顶点的度
11、数之和为d，则e=_。参考答案：d/2 49、 快速排序的最坏时间复杂度为_，平均时间复杂度为_。参考答案：O(n*n)，O(nlog2n) 50、 设一棵完全二叉树中有500个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的存储结构，则共有_个空指针域。参考答案：9，501 51、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT0.12，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。参考答案： 0 1 2 3 4 5 6 7 8 9 10 11 12 7815 03 57 45 20 31 23 36 12 查找成功的平均查找长度：ASL SUCC=14/10= 1.452、写出用直接插入排序将关键字序列54,23,89,48,64,50,25,90,34排序过程的每一趟结果。参考答案：初始：54，23，89，48，64，50，25，90，34 1：（23，54），89，48，64，50，25，90，34 2：（23，54，89），48，64，50，25，90，34 3：（23，48，54，89），64，50，25，90，34 4：（23，48
