《18春西南大学0012]《数据结构》》由会员分享，可在线阅读，更多相关《18春西南大学0012]《数据结构》（18页珍藏版）》请在金锄头文库上搜索。
1、西南大学 网络与继续教育学院 课程代码： 0012 学年学季：20181 单项选择题单项选择题 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则所采用的排序方法是（则所采用的排序方法是（ ）1.A. 选择排序 2.希尔排序 3.快速排序 4.归并排序 2 2、 不定长文件是指（不定长文件是指（ ）1.记
2、录的长度不固定 2.关键字项的长度不固定 3.字段的长度不固定 4.文件的长度不固定 3 3、 如下陈述中正确的是（如下陈述中正确的是（ ）1.串中元素只能是字母 2.串是一种特殊的线性表 3.串的长度必须大于零 4.空串就是空白串 4 4、 将长度为将长度为 n 的单链表链接在长度为的单链表链接在长度为 m 的单链表之后的算法的时间复杂度为（的单链表之后的算法的时间复杂度为（ ）1.O（m+n） 2.O（n） 3.O（m） 4.O（1） 5 5、 设数组设数组 datam作为循环队列作为循环队列 SQ 的存储空间，的存储空间，front 为队头指针，为队头指针，rear 为队尾指针，则为队尾
3、指针，则执行出队操作后其头指针执行出队操作后其头指针 front 值为（值为（ ）1.F. front=(front+1)%m 2.front=(front-1)%m 3.front=front+1 4.front=(front+1)%(m-1) 6 6、计算机算法必须具备输入、输出和、计算机算法必须具备输入、输出和 等等 5 5 个特性个特性1.易读性、稳定性和安全性 2.确定性、有穷性和稳定性 3.可行性、可移植性和可扩充性 4.可行性、确定性和有穷性 5.7 7、有、有 8 8 个结点的无向图最多有个结点的无向图最多有 条边条边1.112 2.56 3.28 4.14 8 8、不含任何结
4、点的空树、不含任何结点的空树1.是一棵树 2.是一棵二叉树 3.是一棵树也是一棵二叉树 4.既不是树也不是二叉树 9 9、一棵深度为、一棵深度为 6 6 的满二叉树有的满二叉树有 个分支结点个分支结点1.30 2.31 3.32 4.33 1010、把一棵树转换为二叉树后，这棵二叉树的形态是、把一棵树转换为二叉树后，这棵二叉树的形态是1.唯一的 2.有多种 3.有多种，但根结点都没有左孩子 4.有多种，但根结点都没有右孩子 1111、在对、在对 n n 个元素的序列进行排序时，堆排序所需要的附加存储空间是个元素的序列进行排序时，堆排序所需要的附加存储空间是: :1.O(log2n) 2.O(1
5、) 3.O(n) 4.O(nlog2n) 1212、若需要在、若需要在 O(nlogO(nlog2 2n)n)的时间内完成对数组的排序，且要求排序是稳定的，则的时间内完成对数组的排序，且要求排序是稳定的，则 可选择的排序方法是（可选择的排序方法是（ ）1.快速排序 2.堆排序 3.归并排序 4.直接插入 1313、设哈希表长、设哈希表长 m=14,m=14,哈希函数哈希函数 H(key)=keyH(key)=key MODMOD 1111。表中已有。表中已有 4 4 个结点：个结点： addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7addr(15)=4,a
6、ddr(38)=5,addr(61)=6,addr(84)=7 其余地址为空，如用二次探其余地址为空，如用二次探 测再散列处理冲突，则关键字为测再散列处理冲突，则关键字为 4949 的地址为的地址为: :1.3 2.5 3.8 4.9 1414、设一棵完全二叉树有、设一棵完全二叉树有 300300 个结点，则共有个结点，则共有 个叶子结点个叶子结点1.150 2.152 3.154 4.156 1515、由个结点所构成的二叉树有、由个结点所构成的二叉树有 种形态种形态. .1.2 2.3 3.4 4.5 1616、设有两个串、设有两个串 p p 和和 q q，求，求 q q 在在 p p 中首
7、次出现的位置的运算称作：中首次出现的位置的运算称作：1.连接 2.模式匹配 3.求子串 4.求串长 1717、 栈中元素的进出原则是栈中元素的进出原则是:1.先进先出 2.后进先出 3.栈空则进 4.栈满则出 1818、链表是一种采用、链表是一种采用 存储结构存储的线性表存储结构存储的线性表. .1.顺序 2.星式 3.链式 4.网状 1919、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的， 称之为：称之为：1.存储结构 2.顺序存储结构 3.逻辑结构 4.链式存储 2020、一个具有、一个具有 n n 个顶点
8、的有向图最多有（个顶点的有向图最多有（ ）条边）条边1.n(n-1)/2 2.n(n+1)/2 3.n(n-1) 4.n2 2121、判断一个循环队列、判断一个循环队列 Q Q（最多（最多 n n 个元素）为满的条件是个元素）为满的条件是: :1.Q-front=(Q-rear+1)%n 2.Q-rear=Q-front+1 3.Q-front=(Q-rear-1)%n 4.Q-rear=Q-front 2222、在单链表中，指针、在单链表中，指针 p p 指向元素为指向元素为 x x 的结点，实现删除的结点，实现删除 x x 的后继的语句是的后继的语句是: :1.p=p-next 2.p=p
9、-next-next 3.p-next=p 4.p-next=p-next-next 2323、在双向循环链表中，在、在双向循环链表中，在 p p 指针所指的结点后插入一个指针指针所指的结点后插入一个指针 q 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-ne
10、xt-prior=q;q-prior=p;q-next=p-next; 2424、 在一棵度为在一棵度为 3 的树中的树中,度为度为 3 的结点个数为的结点个数为 2,度为度为 2 的结点个数为的结点个数为 1,则度为则度为 0 的结点的结点个数为个数为( )1.C. 7 2.6 3.4 4.5 2525、 算法指的是（算法指的是（ ）1.B. 排序算法 2.E. 解决问题的计算方法 3.计算机程序 4.解决问题的有限运算序列 2626、 在含在含 n 个顶点和个顶点和 e 条边的无向图的邻接矩阵中条边的无向图的邻接矩阵中,零元素的个数为零元素的个数为( )1.n*n2e 2.e 3.n*ne
11、 4.2e 2727、 线性表采用链式存储时，结点的存储地址（线性表采用链式存储时，结点的存储地址（ ）1.D. 连续与否均可 2.必须是连续的 3.和头结点的存储地址相连续 4.必须是不连续的 多项选择题多项选择题 2828、抽象数据类型的组成部分分别为、抽象数据类型的组成部分分别为: : 1.数据对象 2.存储结构 3.数据关系 4.基本操作 2929、不具有线性结构的数据结构是：、不具有线性结构的数据结构是： 1.图 2.栈 3.广义表 4.树 3030、算法分析的两个主要方面是、算法分析的两个主要方面是( ( ) ) 1.正确性 2.简单性 3.空间复杂度 4.时间复杂度 判断题判断题
12、 3131、链表的每个结点中都恰好包含一个指针、链表的每个结点中都恰好包含一个指针1.A. 2.B. 3232、如果将所有中国人按照生日来排序，则使用哈希排序算法最快、如果将所有中国人按照生日来排序，则使用哈希排序算法最快1.A. 2.B. 3333、折半查找只适用于有序表，包括有序的顺序表和链表、折半查找只适用于有序表，包括有序的顺序表和链表1.A. 2.B. 3434、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指 针。针。1.A. 2.B. 3535、在单链表中，要访问某个结点，只要知道该结点的地址即可；
13、因此，单链、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链 表是一种随机存取结构。表是一种随机存取结构。1.A. 2.B. 主观题主观题3636、 中序遍历二叉排序树所得到的序列是中序遍历二叉排序树所得到的序列是_序列（填有序或无序）。序列（填有序或无序）。参考答案：参考答案： 有序 3737、若一个线性表中最常用的操作是取第、若一个线性表中最常用的操作是取第 i i 个元素和找第个元素和找第 i i 个元素的前趋元个元素的前趋元 素，则采用（素，则采用（ ）存储方式最节省时间）存储方式最节省时间. .参考答案：参考答案：顺序表3838、 设某无向图中顶点数和边数分别为设某无
14、向图中顶点数和边数分别为 n n 和和 e e，所有顶点的度数之和为，所有顶点的度数之和为 d d，则，则 e=_e=_。参考答案：参考答案：d/2 3939、 快速排序的最坏时间复杂度为快速排序的最坏时间复杂度为_，平均时间复杂度为，平均时间复杂度为_。参考答案：参考答案：O(n*n)，O(nlog2n) 4040、 设一棵完全二叉树中有设一棵完全二叉树中有 500 个结点，则该二叉树的深度为个结点，则该二叉树的深度为_；若用二叉链；若用二叉链表作为该完全二叉树的存储结构，则共有表作为该完全二叉树的存储结构，则共有_个空指针域。个空指针域。参考答案：参考答案：9，501 4141、 为了能有
15、效地应用为了能有效地应用 HASH 查找技术，必须解决的两个问题是查找技术，必须解决的两个问题是_和和_。参考答案：参考答案：构造一个好的 HASH 函数，确定解决冲突的方法 4242、 设有向图设有向图 G 用邻接矩阵用邻接矩阵 Ann作为存储结构，则该邻接矩阵中第作为存储结构，则该邻接矩阵中第 i 行上所有元素行上所有元素之和等于顶点之和等于顶点 i 的的_，第，第 i 列上所有元素之和等于顶点列上所有元素之和等于顶点 i 的的_。参考答案：参考答案：出度，入度 4343、 在一个长度为在一个长度为 n n 的顺序表中删除第的顺序表中删除第 i i 个元素，需要向前移动（个元素，需要向前移动（ ）个）个
