《西安交通大学18年9月课程考试数据结构作业考核试题【答1案】》由会员分享，可在线阅读，更多相关《西安交通大学18年9月课程考试数据结构作业考核试题【答1案】（9页珍藏版）》请在金锄头文库上搜索。
1、西安交通大学 18 年 9 月课程考试数据结构作业考核试题 1、C 2、D 3、C 4、C 5、C 一、单选题共 30 题，60 分1、字符串的长度是指（） A 串中不同字符的个数 B 串中不同字母的个数 C 串中所含字符的个数 D 串中不同数字的个数选择是：C2、两个字符串相等的条件是（ ） 。 A 两串的长度相等； B 两串包含的字符相同； C 两串的长度相等，并且两串包含的字符相同； D 两串的长度相等，并且对应位置上的字符相同。选择是：D3、设顺序循环队列 Q0：M-1的头指针和尾指针分别为 F 和 R，头指针 F 总是指向队头元 素的前一位置，尾指针 R 总是指向队尾元素的当前位置，
2、则该循环队列中的元素个数为 （）AR-F BF-R C(R-F+M)M D(F-R+M)M选择是：C4、对稀疏矩阵进行压缩存储目的是（ ） 。 A 便于进行矩阵运算 B 便于输入和输出 C 节省存储空间 D 降低运算的时间复杂度选择是：C5、用链表表示线性表的优点是（） A 便于随机存取 B 花费的存储空间比顺序表少 C 便于插入与删除 D 数据元素的物理顺序与逻辑顺序相同选择是：C6、执行一趟快速排序能够得到的序列是（） 。 A41，12，34，45，275572，63 B45，34，12，415572，63，27 C63，12，34，45，275541，72 D12，27，45，41553
3、4，63，72选择是：A7、二叉树的第 k 层的结点数最多为（）.A2-1 B2K+1 C2K-1 D2选择是：D8、设顺序线性表中有 n 个数据元素，则删除表中第 i 个元素需要移动（）个元素。An-i Bn+l-i Cn-1-i Di选择是：A9、设指针变量 p 指向双向链表中结点 A，指针变量 s 指向被插入的结点 X，则在结点 A 的 后面插入结点 X 的操作序列为（） Ap-right=s；s-left=p；p-right-left=s；s-right=p-right； Bs-left=p；s-right=p-right；p-right=s；p-right-left=s； Cp-ri
4、ght=s；p-right-left=s；s-left=p；s-right=p-right； Ds-left=p；s-right=p-right；p-right-left=s；p-right=s；选择是：D10、一个非空广义表的表头（） A 不可能是子表 B 只能是子表 C 只能是原子 D 可以是子表或原子选择是：D11、设某哈夫曼树中有 199 个结点，则该哈夫曼树中有（）个叶子结点。A99 B100 C101 D102选择是：B12、一个循环队列一旦说明，其占用空间的大小（ ） 。 A 已固定 B 可以变动 C 不能固定 D 动态变化选择是：A13、设一棵完全二叉树中有 65 个结点，则该
5、完全二叉树的深度为（） 。A8 B7 C6 D5选择是：B14、最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是 （ ） 。A(rear+1) MOD n=front Brear=front Crear+1=front D(rear-l) MOD n=front选择是：B15、若采用邻接矩阵法存储一个 N 个顶点的无向图，则该邻接矩阵是一个（） A 上三角矩阵 B 稀疏矩阵 C 对角矩阵 D 对称矩阵选择是：D16、下面关于线性表的叙述中，错误的是（ ）关系。 A 顺序表必须占一片地址连续的存储单元 B 顺序表可以随机存取任一元素 C 链表不必占用一片地址连
6、续的存储单元 D 链表可以随机存取任一元素选择是：D17、建立一个长度为 n 的有序单链表的时间复杂度为（）AO(n) BO(1) CO(n) DO(log2n)选择是：C18、设指针变量 p 指向单链表中结点 A，若删除单链表中结点 A，则需要修改指针的操作序 列为（） 。 Aq=p-next；p-data=q-data；p-next=q-next；free(q)； Bq=p-next；q-data=p-data；p-next=q-next；free(q)； Cq=p-next；p-next=q-next；free(q)； Dq=p-next；p-data=q-data；free(q)；选择
7、是：A19、二分查找有序表4，6，10，12，20，30，50，70，88，100，若查找表中元素 58， 则它将依次与表中（ ）比较大小，查找结果是失败。 A30，88，70，50 B20，70，30，50 C20，50 D30，88，50选择是：B20、设有 n 个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。A1 Bn Cnlog2n Dn选择是：A21、深度为 h 且有（ ）个结点的二叉树称为满二叉树。A2h-1 B2h C2h-1 D2h选择是：C22、以下数据结构中哪一个是非线性结构？（） A 队列 B 栈 C 线性表 D 二叉树选择是：D23、 AA BB CC DD选
8、择是：B24、设有一个 10 阶的下三角矩阵 A（包括对角线） ，按照从上到下、从左到右的顺序存储 到连续的 55 个存储单元中，每个数组元素占 1 个字节的存储空间，则 A54地址与 A0 0的地址之差为（） 。A10 B19 C28 D55选择是：B25、下列四种排序中（）的空间复杂度最大。 A 插入排序 B 冒泡排序 C 堆排序 D 归并排序选择是：D26、用链表存储的线性表，其优点是（ ） 。 A 便于随机存取 B 花费的存储空间比顺序表少 C 便于插入和删除 D 数据元素的物理顺序与逻辑顺序相同选择是：C27、二路归并排序的时间复杂度为（） 。AO(n) BO(n) CO(nlog2
9、n) DO(1og2n)选择是：C28、链表适用于（ ）查找。 A 顺序 B 二分 C 随机 D 顺序或二分选择是：A29、对一棵二叉排序树进行（ ）遍历，可以得到该二叉树的多有结点按值从小到大排列的 序列。 A 前序 B 中序 C 后序 D 按层次选择是：B30、设某棵三叉树中有 40 个结点，则该三叉树的最小高度为（） 。A3 B4 C5 D6选择是：B二、判断题共 20 题，40 分1、对有序表而言采用二分查找总比采用顺序查找法速度快。 （ ） A 错误B选择是：A2、快速排序是排序算法中平均性能最好的一种排序。 A 错误B选择是：B3、从本质上看，文件是一种非线性结构。 ( ) A 错
10、误B选择是：A4、哈夫曼树中没有度数为 1 的结点。 A 错误B选择是：B5、哈夫曼树中没有度数为 2 的结点。 A 错误B选择是：A6、若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序 遍历序列中的最后一个结点。 A 错误B选择是：B7、栈和队列都是限制存取点的线性结构。 ( ) A 错误B选择是：B8、算法与程序没有区别。 ( ) A 错误B选择是：A9、分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块 号，然后再在相应的块内进行顺序查找。 A 错误B选择是：B10、堆排序所需的时间与待排序的记录个数无关。 （ ） A 错误B选择是：
11、A11、设串 S 的长度为 n,则 S 的子串个数为 n(n+1)/2。 ( ) A 错误B选择是：A12、调用一次深度优先遍历可以访问到图中的所有顶点。 A 错误B选择是：A13、一个完整的算法可以没有输入，但必须有输出。 ( ) A 错误B选择是：B14、由树转化成二叉树，该二叉树的右子树不一定为空。 A 错误B选择是：A15、完全二叉树中的叶子结点只可能在最后两层中出现。 （ ） A 错误B选择是：B16、如果某种排序算法不稳定，则该排序方法就没有实用价值。 （ ） A 错误B选择是：A17、冒泡排序是不稳定的排序。 （ ） A 错误B选择是：A18、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。 A 错误B选择是：B19、 A 错误B选择是：B20、不论线性表采用顺序存储结构还是链式存储结构，删除值为 X 的结点的时间复杂度均 为 O（n） 。 A 错误B选择是：B
