西安交通大学16年9月课程考试《数据结构》作业考核试题

admin

请同学及时保存作业,如您在20分钟内不作操作,系统将自动退出。
西安交通大学16年9月课程考试《数据结构》作业考核试题
试卷总分：100       测试时间：--
       

    单选题
    判断题


一、单选题（共 30 道试题，共 60 分。）
V
1.  设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
A. 99
B. 100
C. 101
D. 102
      满分：2  分
2.  在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行（）。
A. s→link=p→link;p→link=s
B. p→link=s;s→link=q
C. p→link=s→link;s→link=p
D. q→link=s;s→link=p
      满分：2  分
3.  以下数据结构中哪一个是非线性结构？（）
A. 队列
B. 栈
C. 线性表
D. 二叉树
      满分：2  分
4.  树最适合用来表示（）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
      满分：2  分
5.  用链接方式存储的队列，在进行插入运算时（）.
A. 仅修改头指针
B. 头、尾指针都要修改
C. 仅修改尾指针
D. 头、尾指针可能都要修改
      满分：2  分
6.  在一棵具有5层的满二叉树中结点数为（）
A. 31
B. 32
C. 33
D. 16
      满分：2  分
7.  用链接方式存储的队列，在进行插入运算时（）
A. 仅修改头指针
B. 头、尾指针都要修改
C. 仅修改尾指针
D. 头、尾指针可能都要修改
      满分：2  分
8.  在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为（）。
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
      满分：2  分
9.  如下陈述中正确的是（）
A. 串是一种特殊的线性表
B. 串的长度必须大于零
C. 串中元素只能是字母
D. 空串就是空白串
      满分：2  分
10.  设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。
A. O(n)
B. O(n)
C. O(nlog2n)
D. O(1og2n)
      满分：2  分
11.  顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。
A. O(n)
B. O(n)
C. O(n)
D. O(1og2n)
      满分：2  分
12.  设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。
A. n，e
B. e，n
C. 2n，e
D. n，2e
      满分：2  分
13.  在一个顺序存储的循环队列中，队头指针指向队头元素的（）
A. 前一个位置
B. 后一个位置
C. 队头元素位置
D. 队尾元素的前一位置
      满分：2  分
14.  执行一趟快速排序能够得到的序列是（）。
A. [41，12，34，45，27]55[72，63]
B. [45，34，12，41]55[72，63，27]
C. [63，12，34，45，27]55[41，72]
D. [12，27，45，41]55[34，63，72
      满分：2  分
15.  设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。
A. 1
B. 2
C. 3
D. 4
      满分：2  分
16.  设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。
A. 单向链表
B. 单向循环链表
C. 双向链表
D. 双向循环链表
      满分：2  分
17.  线性表采用链式存储时，结点的存储地址（）
A. 必须是不连续的
B. 连续与否均可
C. 必须是连续的
D. 和头结点的存储地址相连续
      满分：2  分
18.  设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。
A. N0=N1+1
B. N0=Nl+N2
C. N0=N2+1
D. N0=2N1+l
      满分：2  分
19.  设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
A. n-i
B. n+l-i
C. n-1-i
D. i
      满分：2  分
20.  若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为（）
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
      满分：2  分
21.  设顺序表的长度为n，则顺序查找的平均比较次数为（）。
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
      满分：2  分
22.  设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
      满分：2  分
23.  设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。
A. 2i+1
B. 2i
C. i/2
D. 2i-1
      满分：2  分
24.  下列四种排序中（）的空间复杂度最大。
A. 插入排序
B. 冒泡排序
C. 堆排序
D. 归并排序
      满分：2  分
25.  设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
A. n-1
B. n
C. n+1
D. 2n-1
      满分：2  分
26.  设完全无向图中有n个顶点，则该完全无向图中有（）条边。
A. n(n-1)/2
B. n(n-1)
C. n(n+1)/2
D. (n-1)/2
      满分：2  分
27.  设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。
A. 129
B. 219
C. 189
D. 229
      满分：2  分
28.  设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。
A. aedfcb
B. acfebd
C. aebcfd
D. aedfbc
      满分：2  分
29.  设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。
A. O(n+e)
B. O(n)
C. O(ne)
D. O(n)
      满分：2  分
30.  设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。
A. 5，3，4，6，1，2
B. 3，2，5，6，4，1
C. 3，1，2，5，4，6
D. 1，5，4，6，2，3
      满分：2  分
请同学及时保存作业,如您在20分钟内不作操作,系统将自动退出。
      



请同学及时保存作业,如您在20分钟内不作操作,系统将自动退出。
西安交通大学16年9月课程考试《数据结构》作业考核试题
试卷总分：100       测试时间：--
       

    单选题
    判断题


二、判断题（共 20 道试题，共 40 分。）
V
1.  哈夫曼树中没有度数为2的结点。
A. 错误
B. 正确
      满分：2  分
2.  对连通图进行深度优先遍历可以访问到该图中的所有顶点。
A. 错误
B. 正确
      满分：2  分
3.  顺序表查找指的是在顺序存储结构上进行查找。
A. 错误
B. 正确
      满分：2  分
4.  中序遍历一棵二叉排序树可以得到一个有序的序列。
A. 错误
B. 正确
      满分：2  分
5.  哈夫曼树中没有度数为1的结点。
A. 错误
B. 正确
      满分：2  分
6.  不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。
A. 错误
B. 正确
      满分：2  分
7.  入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。
A. 错误
B. 正确
      满分：2  分
8.  若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。
A. 错误
B. 正确
      满分：2  分
9.  子串“ABC”在主串“AABCABCD”中的位置为2。
A. 错误
B. 正确
      满分：2  分
10.  图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。
A. 错误
B. 正确
      满分：2  分
11.  冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。
A. 错误
B. 正确
      满分：2  分
12.  非空的双向循环链表中任何结点的前驱指针均不为空。
A. 错误
B. 正确
      满分：2  分
13.  先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
A. 错误
B. 正确
      满分：2  分
14.  对链表进行插入和删除操作时不必移动链表中结点。
A. 错误
B. 正确
      满分：2  分
15.  如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。
A. 错误
B. 正确
      满分：2  分
16.  堆是完全二叉树，完全二叉树不一定是堆。
A. 错误
B. 正确
      满分：2  分
17.  栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。
A. 错误
B. 正确
      满分：2  分
18.  在使用后缀表表示实现计算器时用到一个栈的实例，其作用是暂存运算对象。
A. 错误
B. 正确
      满分：2  分
19.  如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。
A. 错误
B. 正确
      满分：2  分
20.  用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。
A. 错误
B. 正确
      满分：2  分
请同学及时保存作业,如您在20分钟内不作操作,系统将自动退出。
      

mibohua

下载了   怎么打不开