《18春西南大学《数据结构》在线作业》由会员分享，可在线阅读，更多相关《18春西南大学《数据结构》在线作业（8页珍藏版）》请在金锄头文库上搜索。
1、单项选择题 1、 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（ ）A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 单项选择题 2、 不定长文件是指（ ）A. 文件的长度不固定 B. 记录的长度不固定 C. 字段的长度不固定 D. 关键字项的长度不固定 单项选择题 3、 如下陈述中正确的是（ ）A. 串是一种特殊的线性表 B. 串的长度
2、必须大于零 C. 串中元素只能是字母 D. 空串就是空白串 单项选择题 4、 将长度为 n 的单链表链接在长度为 m 的单链表之后的算法的时间复杂度为（ ）A. O（1） B. O（n） C. O（m） D. O（m+n） 单项选择题 5、 设数组 datam作为循环队列 SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其 头指针 front 值为（ ）A. front=front+1 B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m 单项选择题 6、计算机算法必须具备输入、输出
3、和 等 5 个特性A. 易读性、稳定性和安全性 B. 确定性、有穷性和稳定性 C. 可行性、可移植性和可扩充性 D. 可行性、确定性和有穷性 单项选择题 7、有 8 个结点的无向图最多有 条边A. 112 B. 56 C. 28 D. 14 单项选择题 8、不含任何结点的空树A. 是一棵二叉树 B. 是一棵树 C. 是一棵树也是一棵二叉树 D. 既不是树也不是二叉树 单项选择题 9、一棵深度为 6 的满二叉树有 个分支结点A. 30 B. 31 C. 32 D. 33 单项选择题 10、把一棵树转换为二叉树后，这棵二叉树的形态是A. 唯一的 B. 有多种 C. 有多种，但根结点都没有左孩子 D
4、. 有多种，但根结点都没有右孩子 单项选择题 11、在对 n 个元素的序列进行排序时，堆排序所需要的附加存储空间是:A. O(log2n) B. O(1) C. O(n) D. O(nlog2n) 单项选择题 12、若需要在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方 法是（ ）A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入 单项选择题 13、设哈希表长 m=14,哈希函数 H(key)=key MOD 11。表中已有 4 个结点：addr(15)=4,addr(38) =5,addr(61)=6,addr(84)=7 其余地址为空，如用二次
5、探测再散列处理冲突，则关键字为 49 的地址为:A. 3 B. 5 C. 8 D. 9 单项选择题 14、设一棵完全二叉树有 300 个结点，则共有 个叶子结点A. 150 B. 152 C. 154 D. 156 单项选择题 15、由个结点所构成的二叉树有 种形态.A. 2 B. 3 C. 4 D. 5 单项选择题 16、设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作：A. 连接 B. 模式匹配 C. 求子串 D. 求串长 单项选择题 17、 栈中元素的进出原则是:A. 先进先出 B. 后进先出 C. 栈空则进 D. 栈满则出 单项选择题 18、链表是一种采用 存储结构存
6、储的线性表.A. 顺序 B. 星式 C. 链式 D. 网状 单项选择题 19、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：A. 存储结构 B. 顺序存储结构 C. 逻辑结构 D. 链式存储 单项选择题 20、一个具有 n 个顶点的有向图最多有（ ）条边A. n(n-1)/2 B. n(n-1) C. n2 D. n(n+1)/2 单项选择题 21、判断一个循环队列 Q（最多 n 个元素）为满的条件是:A. Q-front=(Q-rear+1)%n B. Q-rear=Q-front+1 C. Q-front=(Q-rear-1)%n D. Q-rear=Q-fron
7、t 单项选择题 22、在单链表中，指针 p 指向元素为 x 的结点，实现删除 x 的后继的语句是:A. p=p-next B. p=p-next-next C. p-next=p D. p-next=p-next-next 单项选择题 23、在双向循环链表中，在 p 指针所指的结点后插入一个指针 q 所指向的新结点，修改指针的 操作是:A. p-next=q;q-prior=p;p-next-prior=q;q-next=q; B. q-prior=p;q-next=p-next;p-next-prior=q;p-next=q; C. q-next=p-next;q-prior=p;p-nex
8、t=q;p-next=q; D. p-next=q;p-next-prior=q;q-prior=p;q-next=p-next; 单项选择题 24、 在一棵度为 3 的树中,度为 3 的结点个数为 2,度为 2 的结点个数为 1,则度为 0 的结点个数为( )A. 4 B. 5 C. 6 D. 7 单项选择题 25、 算法指的是（ ）A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 单项选择题 26、 在含 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为( )A. n*ne B. n*n2e C. e D. 2e 单项选择题 27、 线性表
9、采用链式存储时，结点的存储地址（ ）A. 必须是不连续的 B. 连续与否均可 C. 必须是连续的 D. 和头结点的存储地址相连续 多项选择题 28、抽象数据类型的组成部分分别为:A. 数据对象 B. 存储结构 C. 数据关系 D. 基本操作 多项选择题 29、不具有线性结构的数据结构是：A. 图 B. 栈 C. 广义表 D. 树 多项选择题 30、算法分析的两个主要方面是( )A. 正确性 B. 简单性 C. 空间复杂度 D. 时间复杂度 判断题 31、链表的每个结点中都恰好包含一个指针 A. B. 判断题 32、如果将所有中国人按照生日来排序，则使用哈希排序算法最快 A. B. 判断题 33
10、、折半查找只适用于有序表，包括有序的顺序表和链表 A. B. 判断题 34、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。 A. B. 判断题 35、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结 构。 A. B. 填空题 36、 中序遍历二叉排序树所得到的序列是_序列（填有序或无序） 。 填空题 37、若一个线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用（ ）存 储方式最节省时间. 填空题 38、 设某无向图中顶点数和边数分别为 n 和 e，所有顶点的度数之和为 d，则 e=_。 填空题 39、 快速排序的
11、最坏时间复杂度为_，平均时间复杂度为_。 填空题 40、 设一棵完全二叉树中有 500 个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的 存储结构，则共有_个空指针域。 填空题 41、 为了能有效地应用 HASH 查找技术，必须解决的两个问题是_和 _。 填空题 42、 设有向图 G 用邻接矩阵 Ann作为存储结构，则该邻接矩阵中第 i 行上所有元素之和等于顶点 i 的 _，第 i 列上所有元素之和等于顶点 i 的_。 填空题 43、 在一个长度为 n 的顺序表中删除第 i 个元素，需要向前移动（ ）个元素. 填空题 44、1、已知栈的基本操作函数：int InitStack(Sq
12、Stack *S); /构造空栈int StackEmpty(SqStack *S);/判断栈空int Push(SqStack*S,ElemType e);/入栈int Pop(SqStack *S,ElemType *e);/出栈函数 conversion 实现十进制数转换为八进制数，请将函数补充完整。void conversion()InitStack(S);scanf(“%d”,while(N)（1） ;N=N/8; while( （2） )Pop(S,printf(“%d”,e); /conversion 填空题 45、带头结点的单链表 head 为空的判定条件是（ ） 。 填空题
13、46、 下面程序段的功能实现数据 x 进栈，要求在下划线处填上正确的语句。 typedef struct int s100; int top; sqstack; void push(sqstack else _;_; 填空题 47、 一个循环队列 Q 的存储空间大小为 M,其队头和队尾指针分别为 front 和 rear，则循环队列中元素的个数为：。 填空题 48、 设串长为 n，模式串长为 m，则 KMP 算法所需的附加空间为( ) 应用题 49、 一个线性表为 B=（12，23，45，57，20，03，78，31，15，36） ，设散列表为 HT0.12，散列函数为 H（key）= key
14、 % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找 长度。 应用题 50、写出用直接插入排序将关键字序列54,23,89,48,64,50,25,90,34排序过程的每一趟结果。 应用题 51、 阅读以下二叉树操作算法，指出该算法的功能。 Template void BinTree ： unknown (BinTreeNode*t) BinTreeNode *p =t, *temp;if (p!=NULL) temp = pleftchild;pleftchild = prightchild;prightchild = temp;unknown(pleftc
15、hild);undnown(prightchild); 该算法的功能是：_ 应用题 52、 已知一棵二叉树的前序遍历的结果序列是 ABECKFGHIJ，中序遍历的结果是 EBCDAFHIGJ，试 写出这棵二叉树的后序遍历结果。 应用题 53、 已知一组记录的排序码为（46，79，56，38，40，80, 95，24） ，写出对其进行快速排序的每一次划分结果。应用题 54、设待排序序列为10,18,4,3,6,12,1,9,15,8请写出希尔排序每一趟的结果。增量序列为 5，3，2，1。 应用题 55、写出下列程序的时间复杂度s=0;for i=0; ifront=(Q-rear+1)%n B. Q-rear=Q-front+1 C. Q-front=(Q-rear-1)%
