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