西南大学网络教育2018年春[0012]《数据结构》答案

《西南大学网络教育2018年春[0012]《数据结构》答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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.选择排序・希尔排序.快速排序匸・归并排序不定长文件是指（）记录的长度不固定关键字项的长度不固定字段的长度不固定文件的长度不固定23、如下陈述中正确的是（）串中元索只能是字母9串是一种特殊的线性农串的长度必须大于零空串就是空白串将长度为n的单链表链接在长度为m的单链表之

2、后的算法的时间复杂度为（O(m+n)O(n)O(m)O(1)95.设数组data

3、m

4、作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）F.fiont=(fi-ont+l)%mfront=(front-1)%mfront=fiont-i-lfront=(front+1)%(m-l)6、计算机算法必须具备输入、输岀和_等5个特性・易读性、稳定性和安全性・确定性、有穷性和稳定性・可行性、可移植性和可扩充性・可行性、确定性和有穷性97、有8个结点的无向图最多有_条边・112・56・289.148、不含任何结点的空树・是一

5、棵树・是一棵二叉树.是一棵树也是一棵二叉树y・既不是树也不是二叉树9、一棵深度为6的满二叉树有—个分支结点・30・319・32・3310、把一棵树转换为二叉树后，这棵二叉树的形态是・唯一的9・有多种・有多种，但根结点都没有左孩子.有多种，但根结点都没有右孩子11、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是：・O(log2n)・0(1)9・O(n)・O(nlog2n)12、若需要在O(nlogln)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是()・快速排序・堆排序.归并排序9・直接插入13、设哈希表长m=14,哈希函数H(key)=keyM

6、OD11o表中已有4个结点:・3・5・89・914、设一棵完全二叉树有3U0个结点，则共有—个叶子结点・1509・152・154・15615、由3个结点所构成的二叉树有种形态.・2・3・45916、设有两个串p和q,求q在p中首次出现的位置的运算称作：・连接・模式匹配9・求子出・求串长addr(⑸=^addr(38)=5,addr(61)=6,addr(84)=7其余地址为空，如用二次探测再散列处理冲突栈中元素的进出原则是：・先进先出・后进先出°・栈空则进・栈满则出18、链表是一种采用—存储结构存储的线性表..顺序・星式.链式9・网状19、数据在计算机存储器内表示时，物理地址

7、与逻辑地址相同并且是连续的，称之为:・存储结构・顺序存储结构9・逻辑结构・链式存储20、一个具有n个顶点的有向图最多有()条边・nx(n-l)/2・nx(n+l)/29・nx(n-l)・n221、判断一个循环队列Q(最多n个元素)为满的条件是:■■■•Q->fiont==(Q->rear+1)%nWQ->rcar==Q->front+1Q->front==(Q->rear-1)%nQ->rear==Q->front22、•■■■在单链表中，指针p指向元素为X的结点，实现删除X的后继的语句是：p=p・>nextp=p・>next・>nextp->ncxt=pp->next=p-

8、>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;9q->next=p->next;q->prior=p;p->next=q;p・>ncxt=q;p->ncxt=q;p・>ncxt・>prior=q;q->prior=p;q->ncxt=p・>next;24.在一棵度为3的树中，度为3的结点个数为2,度为

9、2的结点个数为1侧度为0的结点个数为（）C.76425、算法指的是（）・B.排序算法・E.解决问题的计算方法・计算机程序・解决问题的有限运算序列926、在含n个顶点和c条边的无向图的邻接矩阵中，零元素的个数为（）•n*n—2e•e•n*n—e•2e线性表采用链式存储时，结点的存储地址（）D.连续与否均可必须是连续的和头结点的存储地址相连续匸必须是不连续的多项选择题28、抽象数据类型的组成部分分别为:・数据对象9.存储结构・数据关系9.基本操作°29、不具有线性结构的数据结构是：・图9・栈・广义表9・树&