数据结构与算法中国大学mooc作业答案

日期:2021-12-07 06:42:13

1 绪论

1.1  什么是数据结构随堂测验

1、在链接存储结构中,要求 。
    A、每个结点占用一片连续的存储区域
    B、所有结点占用一片连续的存储区域
    C、结点的最后一个域是指针类型
    D、每个结点有多少个后继就设多少个指针

2、对于数据结构的描述,下列说法中不正确的是 。
    A、相同的逻辑结构对应的存储结构也必须相同
    B、数据结构由逻辑结构、存储结构和基本操作三个方面构成
    C、数据结构基本操作的实现与存储结构有关
    D、数据的存储结构是数据的逻辑结构的机内实现

3、以下关于链接存储结构的叙述中, 是不正确的。
    A、结点除数据信息外还包括指针域,因此存储密度小于顺序存储结构
    B、逻辑上相邻的结点在物理上不一定相邻
    C、可以通过计算得到第i个节点的存储地址
    D、插入和删除操作方便,不必移动结点

4、可以用 、数据关系和基本操作定义一个完整的抽象数据类型。
    A、数据元素
    B、数据对象
    C、原子类型
    D、存储结构

5、顺序存储结构中数据元素之间的逻辑关系是由 表示的,链接存储结构中的数据元素之间的逻辑关系式由 表示的。
    A、线性结构
    B、非线性结构
    C、存储位置
    D、指针

1.2 算法设计与分析随堂测验

1、算法指得是 。
    A、对特定问题求解步骤的一种描述,是指令的有限序列。
    B、计算机程序
    C、解决问题的计算方法
    D、数据处理

2、下面 不是算法所必须具备的特性。
    A、有穷性
    B、确切性
    C、高效性
    D、可行性

3、某算法的时间复杂度是O(n^2),表明该算法 。
    A、问题规模是n^2
    B、执行时间等于n^2
    C、执行时间与n^2成正比
    D、问题规模与n^2成正比

4、设某算法完成对n个元素进行处理,所需的时间是T(n)=100nlgn+200n+500,则该算法的时间复杂度是 。
    A、O(1)
    B、O(n)
    C、O(nlgn)
    D、O(nlgn)+O(n)

5、算法的时间复杂度属于一种 。
    A、事前统计的方法
    B、事前分析估算的方法
    C、事后统计的方法
    D、事后分析估算的方法

绪论单元测验

1、在链接存储结构中,要求 。
    A、每个结点占用一片连续的存储区域
    B、所有结点占用一片连续的存储区域
    C、结点的最后一个域是指针类型
    D、每个结点有多少个后继就设多少个指针

2、对于数据结构的描述,下列说法中不正确的是 。
    A、相同的逻辑结构对应的存储结构也必须相同
    B、数据结构由逻辑结构、存储结构和基本操作三个方面构成
    C、数据结构基本操作的实现与存储结构有关
    D、数据的存储结构是数据的逻辑结构的机内实现

3、以下关于链接存储结构的叙述中, 是不正确的。
    A、结点除数据信息外还包括指针域,因此存储密度小于顺序存储结构
    B、逻辑上相邻的结点在物理上不一定相邻
    C、可以通过计算得到第i个节点的存储地址
    D、插入和删除操作方便,不必移动结点

4、可以用 、数据关系和基本操作定义一个完整的抽象数据类型。
    A、数据元素
    B、数据对象
    C、原子类型
    D、存储结构

5、算法指得是 。
    A、对特定问题求解步骤的一种描述,是指令的有限序列
    B、计算机程序
    C、解决问题的计算方法
    D、数据处理

6、下面 不是算法所必须具备的特性。
    A、有穷性
    B、确切性
    C、高效性
    D、可行性

7、某算法的时间复杂度是O(n^2),表明该算法 。
    A、问题规模是n^2
    B、执行时间等于n^2
    C、执行时间与n^2成正比
    D、问题规模与n^2成正比

8、设某算法完成对n个元素进行处理,所需的时间是T(n)=100nlgn+200n+500,则该算法的时间复杂度是 。
    A、O(1)
    B、O(n)
    C、O(nlgn)
    D、O(nlgn)+O(n)

9、算法的时间复杂度属于一种 。
    A、事前统计的方法
    B、事前分析估算的方法
    C、事后统计的方法
    D、事后分析估算的方法

绪论单元作业

1、简述逻辑结构与存储结构的关系。

2、度量一个算法的执行时间通常有几种方法?各有何优缺点?

3、分析下面函数的时间复杂度。 void func(int n) { int i = 1, k = 100; while(i < n) { k++; i+=2; } }

2 线性表

2.1 线性表及其顺序存储随堂测验

1、将两个各有n个元素的有序顺序表归并成一个有序顺序表,其最少的比较次数是 。
    A、n
    B、2n-1
    C、2n
    D、n-1

2、在长度为n的线性表中查找值为x的数据元素的时间复杂度为 。
    A、O(0)
    B、O(1)
    C、O(n)
    D、O(n^2)

3、线性表的顺序存储结构是一种 的存储结构。
    A、随机存取
    B、顺序存取
    C、索引存取
    D、散列存取

4、在一个长度为n的顺序表的第i(1≤i≤n+1)个元素之前插入一个元素,需向后移动 个元素,删除第i(1≤i≤n)个元素时,需向前移动 个元素。
    A、n-i
    B、n-i+1
    C、n-i
    D、n-i+1

2.2  链表随堂测验

1、设线性表中有2n个元素,以下操作中, 在单链表上实现要比在顺序表上实现效率更高。
    A、删除指定的元素
    B、在最后一个元素的后面插入一个新元素
    C、顺序输出前k个元素
    D、交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1)

2、如果最常用的操作是取第i个节点及其前驱,则采用 存储方式最节省时间。
    A、单链表
    B、双链表
    C、单循环链表
    D、顺序表

3、与单链表相比,双链表的优点之一是 。
    A、插入、删除操作更简单
    B、可以进行随机访问
    C、可以省略表头指针或表尾指针
    D、访问前后相邻结点更灵活

4、带头结点的单链表L为空的判定条件是 。
    A、L==NULL
    B、L->next==NULL
    C、L->next==L
    D、L!=NULL

5、在一个单链表中,已知q所指结点是p所指结点的直接前驱,若在q和p之间插入s所指结点,则执行 操作。
    A、s->next=p->next ; p->next=s;
    B、q->next=s ; s->next=p;
    C、p->next=s->next ; s->next=p;
    D、p->next=s ; s->next=q;

6、设指针rear指向带头结点的循环单链表的尾结点,若要删除链表的第一个元素结点,正确的操作是 。
    A、s=rear ; rear=rear->next;
    B、rear=rear->next;
    C、rear=rear->next->next;
    D、s=rear->next->next ; rear->next->next=s->next;

2.3  栈的基本概念与存储随堂测验

1、经过以下栈运算后,x的值是 。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);
    A、a
    B、b
    C、0
    D、1

2、一个栈的进栈a,b,c,d,e则栈的不可能的输出序列是 。
    A、edcba
    B、decba
    C、dceab
    D、abcde

3、已知一个栈的进栈序列是ABC,出栈序列是CBA,经过的栈操作是 。
    A、push,pop,push,pop,push,pop
    B、push,push,push,pop,pop,pop
    C、push,push,pop,pop,push,pop
    D、push,pop,push,push,pop,pop

4、判定一个顺序栈st为(元素个数最多为MaxSize)空的条件为 。
    A、st.top==-1
    B、st.top!=-1
    C、st.top!=MaxSize
    D、st.top==MaxSize

5、链栈与顺序栈相比有一个明显的优点,即 。
    A、插入操作更方便
    B、通常不会出现栈满的情况
    C、不会出现栈空的情况
    D、删除操作更加方便

2.5 队列随堂测验

1、设环形队列中数组的下标是0~N-1,其头、尾指针分别为f和r,则其元素个数为 。
    A、r-f
    B、r-f-1
    C、(r-f)%N+1
    D、(r-f+N)%N

2、对于链队,在进行删除操作时, 。
    A、仅修改头指针
    B、仅修改尾指针
    C、头、尾指针都要修改
    D、头、尾指针可能都要修改

2.6 字符串匹配随堂测验

1、两个串相等必有串长度相等且 。
    A、串的各位置字符任意
    B、串中各位置字符均对应相等
    C、两个串含有相同的字符
    D、两个所含字符任意

2、对于含有n个字符的链串s,查找元素值为x的算法时间复杂度为 。
    A、O(1)
    B、O(n)
    C、O(n^2)
    D、O(lgn)

3、设有两个串p和q,求q在p中首次出现的位置的运算称作 。
    A、连接
    B、模式匹配
    C、求子串
    D、求串长

2.7 字符串的模式匹配——KMP算法随堂测验

1、已知t=”abcaabbcabcaabdab”,该模式串的特征数组值为 。
    A、-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1
    B、0,1,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1
    C、-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,7,1
    D、-1,0,0,0,1,1,2,3,0,1,2,3,4,5,6,0,1

线性表单元测验

1、将两个各有n个元素的有序顺序表归并成一个有序顺序表,其最少的比较次数是 。
    A、n
    B、2n-1
    C、2n
    D、n-1

2、在长度为n的线性表中查找值为x的数据元素的时间复杂度为 。
    A、O(0)
    B、O(1)
    C、O(n)
    D、O(n^2)

3、线性表的顺序存储结构是一种 的存储结构。
    A、随机存取
    B、顺序存取
    C、索引存取
    D、散列存取

4、设线性表中有2n个元素,以下操作中, 在单链表上实现要比在顺序表上实现效率更高。
    A、删除指定的元素
    B、在最后一个元素的后面插入一个新元素
    C、顺序输出前k个元素
    D、交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1)

5、如果最常用的操作是取第i个节点及其前驱,则采用 存储方式最节省时间。
    A、单链表
    B、双链表
    C、单循环链表
    D、顺序表

6、与单链表相比,双链表的优点之一是 。
    A、插入、删除操作更简单
    B、可以进行随机访问
    C、可以省略表头指针或表尾指针
    D、访问前后相邻结点更灵活

7、带头结点的单链表L为空的判定条件是 。
    A、L==NULL
    B、L->next==NULL
    C、L->next==L
    D、L!=NULL

8、在一个单链表中,已知q所指结点是p所指结点的直接前驱,若在q和p之间插入s所指结点,则执行 操作。
    A、s->next=p->next ; p->next=s;
    B、q->next=s ; s->next=p;
    C、p->next=s->next ; s->next=p;
    D、p->next=s ; s->next=q;

9、设指针rear指向带头结点的循环单链表的尾结点,若要删除链表的第一个元素结点,正确的操作是 。
    A、s=rear ; rear=rear->next;
    B、rear=rear->next;
    C、rear=rear->next->next;
    D、s=rear->next->next ; rear->next->next=s->next;

10、经过以下栈运算后,x的值是 。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);
    A、a
    B、b
    C、0
    D、1

11、一个栈的进栈a,b,c,d,e则栈的不可能的输出序列是 。
    A、edcba
    B、decba
    C、dceab
    D、abcde

12、已知一个栈的进栈序列是ABC,出栈序列是CBA,经过的栈操作是 。
    A、push,pop,push,pop,push,pop
    B、push,push,push,pop,pop,pop
    C、push,push,pop,pop,push,pop
    D、push,pop,push,push,pop,pop

13、判定一个顺序栈st为(元素个数最多为MaxSize)空的条件为 。
    A、st.top==-1
    B、st.top!=-1
    C、st.top!=MaxSize
    D、st.top==MaxSize

14、链栈与顺序栈相比有一个明显的优点,即 。
    A、插入操作更方便
    B、通常不会出现栈满的情况
    C、不会出现栈空的情况
    D、删除操作更加方便

15、设环形队列中数组的下标是0~N-1,其头、尾指针分别为f和r,则其元素个数为 。
    A、r-f
    B、r-f-1
    C、(r-f)%N+1
    D、(r-f+N)%N

16、对于链队,在进行删除操作时, 。
    A、仅修改头指针
    B、仅修改尾指针
    C、头、尾指针都要修改
    D、头、尾指针可能都要修改

17、对于含有n个字符的链串s,查找元素值为x的算法时间复杂度为 。
    A、O(1)
    B、O(n)
    C、O(n^2)
    D、O(lgn)

18、已知t=”abcaabbcabcaabdab”,该模式串的特征数组值为 。
    A、-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1
    B、0,1,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1
    C、-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,7,1
    D、-1,0,0,0,1,1,2,3,0,1,2,3,4,5,6,0,1

线性表单元作业

1、在带头结点的单链表L中,删除所有值为x的结点,假设值为x的结点不唯一,试编写算法以实现上述操作。

2、从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素。

3、有5个元素,其入栈次序为A、B、C、D、E,在各种可能的出栈次序中,第一个出栈元素为C且第二个出栈元素为D的出栈序列有哪几个?(请分别列出)

3 二叉树

3.1 二叉树的概念与性质随堂测验

1、若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是
    A、9
    B、11
    C、15
    D、不确定

2、具有10个叶结点的二叉树中有 个度为2的结点。
    A、8
    B、9
    C、10
    D、11

3、一棵完全二叉树上有1001个结点,其中叶子结点的个数是 。
    A、250
    B、501
    C、254
    D、505

4、二叉树的第I(只有根结点时的层数为1)层上最多含有结点数为 。
    A、2^I
    B、2^(I-1)-1
    C、2^(I-1)
    D、2^I-1

5、一个具有1025个结点的二叉树的高h(只有根结点时的高度为1)为
    A、11
    B、10
    C、11至1025之间
    D、10至1024之间

6、一棵二叉树高度为h(只有根结点时的高度为1),所有结点的度或为0,或为2,则这棵二叉树最少有 结点
    A、2h
    B、2h-1
    C、2h+1
    D、h+1

7、高度为 K(只有根结点时的高度为1)的二叉树最大的结点数为 。
    A、2^k
    B、2^(k-1)
    C、2^k-1
    D、2^(k-1)-1

8、一棵树高为K(只有根结点时的高度为1)的完全二叉树至少有 个结点
    A、2^k-1
    B、2^(k-1)-1
    C、2^(k-1)
    D、2^k

9、由3个结点所构成的二叉树有 种形态。

3.2 二叉树的存储随堂测验

1、二叉树是非线性数据结构,所以 。
    A、它不能用顺序存储结构存储
    B、它不能用链式存储结构存储
    C、顺序存储结构和链式存储结构都能存储
    D、顺序存储结构和链式存储结构都不能使用

2、对于任意非空二叉树,要设计出其后序遍历的非递归算法而不是用堆栈结构,最适合的方法是对该二叉树采用 存储结构。
    A、三叉链表
    B、二叉链表
    C、顺序
    D、索引

3.4 二叉树的遍历(二)随堂测验

1、一直二叉树的先序序列为ABDECF,中序序列为DBEAFC,则后序序列为 。
    A、DEBAFC
    B、DEFBCA
    C、DEBCFA
    D、DEBFCA

2、用一维数组存放的一棵完全二叉树ABCDEFGHIJKL,该二叉树的后序遍历的访问结点序列为 。

3.6 堆与优先队列随堂测验

1、设字符A,B,C,D,E,F的在报文中出现的频率分别为0.25,0.2,0.06,0.14,0.28,0.07。求A 的Huffman编码。

2、(续)求B的Huffman编码。

3、(续)求C的Huffman编码。

4、(续)求D的Huffman编码。

5、(续)求E的Huffman编码。

6、(续)求F的Huffman编码。

3.7 Huffman树及其应用随堂测验

1、有n个叶子的哈夫曼树的结点总数为 。
    A、不确定
    B、2n
    C、2n+1
    D、2n-1

2、下面关于Huffman树的说法,不正确的是 。
    A、对应与一组权值构造出的Huffman树一般不是唯一的
    B、Huffman树具有最小权值路径长度
    C、Huffman树中没有度为1的结点
    D、Huffman树中除了度为1的结点外,还有度为2的结点和叶结点

二叉树单元测验

1、若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是 。
    A、9
    B、11
    C、15
    D、18

2、具有10个叶结点的二叉树中有 个度为2的结点。
    A、8
    B、9
    C、10
    D、11

3、一棵完全二叉树上有1001个结点,其中叶子结点的个数是 。
    A、250
    B、501
    C、254
    D、505

4、二叉树的第I(只有根结点时的层数为1)层上最多含有结点数为 。
    A、2^l
    B、2^(l-1)-1
    C、2^(l-1)
    D、2^l-1

5、一个具有1025个结点的二叉树的高h(只有根结点时的高度为1)为
    A、11
    B、10
    C、11至1025之间
    D、10至1024之间

6、一棵二叉树高度为h(只有根结点时的高度为1),所有结点的度或为0,或为2,则这棵二叉树最少有 结点
    A、2h
    B、2h-1
    C、2h+1
    D、h+1

7、高度为 K(只有根结点时的高度为1)的二叉树最大的结点数为 。
    A、2^k
    B、2^(k-1)
    C、2^k-1
    D、2^(k-1)-1

8、一棵树高为K(只有根结点时的高度为1)的完全二叉树至少有 个结点
    A、2^k-1
    B、2^(k-1)-1
    C、2^(k-1)
    D、2^k

9、二叉树是非线性数据结构,所以 。
    A、它不能用顺序存储结构存储
    B、它不能用链式存储结构存储
    C、顺序存储结构和链式存储结构都能存储
    D、顺序存储结构和链式存储结构都不能使用

10、对于任意非空二叉树,要设计出其后序遍历的非递归算法而不是用堆栈结构,最适合的方法是对该二叉树采用 存储结构。
    A、三叉链表
    B、二叉链表
    C、顺序
    D、索引

11、一直二叉树的先序序列为ABDECF,中序序列为DBEAFC,则后序序列为 。
    A、DEBAFC
    B、DEFBCA
    C、DEBCFA
    D、DEBFCA

12、有n个叶子的哈夫曼树的结点总数为 。
    A、不确定
    B、2n
    C、2n+1
    D、2n-1

13、下面关于Huffman树的说法,不正确的是 。
    A、对应与一组权值构造出的Huffman树一般不是唯一的
    B、Huffman树具有最小权值路径长度
    C、Huffman树中没有度为1的结点
    D、Huffman树中除了度为1的结点外,还有度为2的结点和叶结点

14、二叉树的先序遍历的递归实现如下: template<class T> void BinaryTree<T>::PreOrder (BinaryTreeNode<T> *root) { if (root != NULL) { ; } } 则中间部分应为:
    A、Visit(root->value());PreOrder(root->leftchild());PreOrder(root->rightchild());
    B、PreOrder(root->leftchild());Visit(root->value());PreOrder(root->rightchild());
    C、PreOrder(root->rightchild());Visit(root->value());PreOrder(root->leftchild());
    D、PreOrder(root->leftchild());PreOrder(root->rightchild());Visit(root->value());

15、在任何一棵二叉树中,如果结点a 有左孩子b, 右孩子c , 则在结点的先序序列、中序序列、后序序列中,
    A、结点b 一定在结点a 的前面
    B、结点a 一定在结点c 的前面
    C、结点b 一定在结点c 的前面
    D、结点a 一定在结点b 的前面

16、在二叉树的前序序列、中序序列和后序序列中,所有叶子结点的先后顺序
    A、都不相同
    B、完全相同
    C、前序和中序相同,而后序不同
    D、中序和后序相同,而前序不同

17、设n、m为一棵二叉树上的两个结点,在中序遍历时,n在m前的条件是
    A、n 在m 右方
    B、n 是m祖先
    C、n 在m 左方
    D、n 是m 子孙

18、下列序列中,不能唯一地确定一棵二叉树的是
    A、层次序列和中序序列
    B、先序序列和中序序列
    C、后序序列和中序序列
    D、先序序列和后序序列

19、设结点X 和Y 是二叉树中任意的两个结点. 在该二叉树的先序遍历序列中X 在Y 之前,而在其后序遍历序列中X 在Y 之后,则X 和Y 的关系是
    A、X 是Y 的左兄弟
    B、X 是Y 的右兄弟
    C、X 是Y 的祖先
    D、X 是Y 的后代

20、一棵二叉树的前序遍历序列为1234567 , 它的中序遍历序列可能是
    A、3124567
    B、1234567
    C、4135627
    D、1463572

21、在二叉搜索树的存储结构中,关键字值最大的结点()
    A、左指针一定为空
    B、右指针一定为空
    C、左右指针均为空
    D、左右指针均不为空

22、对于下列关键字序列,不可能构成某二叉搜索树中的一条查找路径的序列是()
    A、95,22,91,24,94,71
    B、92,20,91,34,88,35
    C、21,89,77,29,36,38
    D、12,25,71,68,33,34

23、从空树开始一次插入元素52,26,14,32,71,60,93,58,24,41后构成一个二叉搜索树。在该树中查找60要进行比较的次数是()
    A、3
    B、4
    C、5
    D、6

24、对于二叉搜索树,下面说法正确的是()
    A、二叉搜索树是动态树表,查找失败时或插入新结点时,会引起数的重新分裂组合
    B、对二叉搜索树进行层次遍历可得到有序序列
    C、用逐点插入法构造二叉搜索树,若先后插入的关键字有序,二叉搜索树的深度最大
    D、在二叉搜索树中进行查找,关键字比较的次数不超过结点数的1/2

25、设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。 
    A、2m-1
    B、2m
    C、2m+1
    D、4m

26、根据使用频率为五个字符设计的哈夫曼编码不可能是__。 
    A、111,110,10,01,00 
    B、000,001,010,011,1 
    C、100,11,10,1,0 
    D、001,000,01,11,10

27、设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有(    )个。
    A、n-1
    B、n
    C、n+1
    D、n+2

28、设森林F对应的二叉树为B,它有m个结点,B的根为P,P的右子树结点个数为n,森林F中的第一棵树的结点个数是__。 
    A、m-n
    B、m-n-1
    C、n+1
    D、条件不充分,无法确定

29、度为4、高度为h的树,__。 
    A、至少有h+3个结点
    B、至多有4h-1个结点
    C、至多有4h个结点
    D、至多有4h个结点  D)至少有h+4个结点

30、设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是(    )。
    A、M1
    B、M1+M2
    C、M3
    D、M2+M3

二叉树单元作业

1、已知一棵度为4的树中,其度为0、1、2、3的结点数分别为14、4、3、2,求该树的结点总数n和度为4的结点个数,并给出推导过程。

2、已知完全二叉树的第9层有240个结点,则整个完全二叉树有多少个结点?有多少个叶子结点?

3、试给出二叉树的自下而上、从右到左的层次遍历算法。

4 图

4.1 图的基本概念随堂测验

1、设图G有n个结点,m条边,且G中每个结点的度数不是k,就是k+1,则G中度数为k的节点数是 。
    A、n/2
    B、n(n+1)
    C、nk-2m
    D、n(k+1)-2m

2、设无向图的顶点个数为n,则该图最多有 条边。
    A、n-1
    B、n(n-1)/2
    C、n(n+1)/2
    D、n^2

4.2 图的存储随堂测验

1、下列说法正确的是 。
    A、有向图的邻接矩阵是对称的。
    B、无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵。
    C、邻接矩阵适用于有向图和无向图的存储,但不能存储带权的有向图和无向图,而只能使用邻接表存储形式来存储它。
    D、用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结点个数有关,而与图的边数无关。

4.3 图的遍历随堂测验

1、下列说法不正确的是 。
    A、图的遍历是从给定的源点出发每一个顶点仅被访问一次
    B、遍历的基本算法有两种:深度遍历和广度遍历
    C、图的深度遍历不适用于有向图
    D、图的深度遍历是一个递归过程

2、无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d), (e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是 。
    A、a,b,e,c,d,f
    B、a,c,f,e,b,d
    C、a,e,b,c,f,d
    D、a,e,d,f,c,b

3、判断一个有向图是否存在回路除了可以使用拓扑排序方法外,还可以使用 方法。
    A、求关键路径
    B、Dijkstra
    C、广度优先遍历
    D、深度优先遍历

4.4 最小生成树随堂测验

1、在用Kruskal算法求解带权连通图的最小生成树时,通常采用一个 辅助结构。
    A、位向量
    B、堆
    C、并查集
    D、生成树顶点集合

2、下列说法正确的是
    A、每个带权图都有唯一的最小生成树。
    B、连通图上各边权值均不相同,则该图的最小生成树可能有多个。
    C、求最小生成树的Prim算法中边上的权可正可负。
    D、最小生成树的Kruskal算法是一种贪心算法。

4.5 最短路径随堂测验

1、下列说法不正确的是 。 (1). 求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义; (2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3) ;(图用邻接矩阵表示) (3). Floyd 求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。
    A、(1),(2),(3)
    B、(1)
    C、(1),(3)
    D、(2),(3)

4.6 关键路径随堂测验

1、关键路径是事件结点网络中 。
    A、从源点到汇点的最长路径
    B、从源点到汇点的最短路径
    C、最长回路
    D、最短回路

2、下面关于求关键路径的说法不正确的是 。
    A、求关键路径是以拓扑排序为基础的
    B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
    C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
    D、关键活动一定位于关键路径上

图单元测验

1、设图G有n个结点,m条边,且G中每个结点的度数不是k,就是k+1,则G中度数为k的节点数是 。
    A、n/2
    B、n(n+1)
    C、nk-2m
    D、n(k+1)-2m

2、设无向图的顶点个数为n,则该图最多有 条边。
    A、n-1
    B、n(n-1)/2
    C、n(n+1)/2
    D、n^2

3、下列说法正确的是 。
    A、有向图的邻接矩阵是对称的。
    B、无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵。
    C、邻接矩阵适用于有向图和无向图的存储,但不能存储带权的有向图和无向图,而只能使用邻接表存储形式来存储它。
    D、用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结点个数有关,而与图的边数无关。

4、下列说法不正确的是 。
    A、图的遍历是从给定的源点出发每一个顶点仅被访问一次
    B、遍历的基本算法有两种:深度遍历和广度遍历
    C、图的深度遍历不适用于有向图
    D、图的深度遍历是一个递归过程

5、无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d), (e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是 。
    A、a,b,e,c,d,f
    B、a,c,f,e,b,d
    C、a,e,b,c,f,d
    D、a,e,d,f,c,b

6、判断一个有向图是否存在回路除了可以使用拓扑排序方法外,还可以使用 方法。
    A、求关键路径
    B、Dijkstra
    C、广度优先遍历
    D、深度优先遍历

7、在用Kruskal算法求解带权连通图的最小生成树时,通常采用一个 辅助结构。
    A、位向量
    B、堆
    C、并查集
    D、生成树顶点集合

8、下列说法正确的是
    A、每个带权图都有唯一的最小生成树
    B、连通图上各边权值均不相同,则该图的最小生成树可能有多个
    C、求最小生成树的Prim算法中边上的权可正可负
    D、最小生成树的Kruskal算法是一种贪心算法

9、下列说法不正确的是 。 (1). 求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义; (2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3) ;(图用邻接矩阵表示) (3). Floyd 求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。
    A、(1),(2),(3)
    B、(1)
    C、(1),(3)
    D、(2),(3)

10、关键路径是事件结点网络中 。
    A、从源点到汇点的最长路径
    B、从源点到汇点的最短路径
    C、最长回路
    D、最短回路

11、下面关于求关键路径的说法不正确的是 。
    A、求关键路径是以拓扑排序为基础的
    B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
    C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
    D、关键活动一定位于关键路径上

12、一个有n个顶点和n条边的无向图一定是()。
    A、连通的
    B、不连通的
    C、无环的
    D、有环的

13、若邻接表中有奇数个边表结点,则一定是()
    A、图中有奇数个结点
    B、图中有偶数个结点
    C、图为无向图
    D、图为有向图

14、用邻接表存储的图的深度优先遍历算法类似于树的()
    A、中序遍历
    B、先序遍历
    C、后序遍历
    D、层次遍历

15、设有向图G=(V, E),顶点集V={V0,V1,V2,V3},边集 E={<v0,v1>,<v0,v2>,<v0,v3>,<v1,v3>}。 若从顶点V0开始对图进行深度优先遍历,则 可能得到的不同遍历序列个数是()
    A、2
    B、3
    C、4
    D、5

16、任何一个无向连通图的最小生成树()。
    A、有一棵或多棵
    B、只有一棵
    C、一定有多棵
    D、可能不存在

17、下列关于最小生成树的叙述中,正确的是()。 Ⅰ 最小生成树的代价唯一 Ⅱ 所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ 使用Prim算法从不同顶点开始得到的最小生成树一定相同 Ⅳ 使用Prim算法和Kruskal算法得到最小生成树总不相同
    A、仅Ⅰ
    B、仅Ⅱ
    C、仅Ⅰ、Ⅲ
    D、仅Ⅱ、Ⅳ

18、用DFS 遍历一个无环有向图,并在DFS 算法退栈返回时打印相应的顶点,则输出的顶点序列是( )。
    A、逆拓扑有序
    B、拓扑有序
    C、无序的
    D、以上都不对

19、要连通具有n个顶点的有向图,至少需要( )条边。
    A、n-1
    B、n
    C、n+1
    D、2n

20、用相邻矩阵A表示图,判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连,则只要检查( )的第i行第j列的元素是否为零即可。
    A、mA
    B、A
    C、Am
    D、Am-1

21、在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为( )。
    A、O(n)
    B、O(n+e)
    C、O(n^2)
    D、O(n^3)

22、求解最短路径的Floyd算法的时间复杂度为( )。
    A、O(n)
    B、O(n+c)
    C、O(n*n)
    D、O(n*n*n)

23、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是( )。
    A、V1,V3,V4,V6,V2,V5,V7
    B、V1,V3,V2,V6,V4,V5,V7
    C、V1,V3,V4,V5,V2,V6,V7
    D、V1,V2,V5,V3,V4,V6,V7

24、在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是()。
    A、G中有弧<Vi,Vj>
    B、G中有一条从Vi到Vj的路径
    C、G中没有弧<Vi,Vj>
    D、G中有一条从Vj到Vi的路径

图单元作业

1、图G是一个非连通无向图,共有28条边,则该图至少有多少个顶点?

2、若某带权图为G=(V,E),其中V={v1,v2,v3,v4,v5,v6,v7,v8,v9,v10},E={<v1,v2>5,<v1,v3>6,<v2,v5>3,<v3,v5>6,<v3,v4>3,<v4,v5>3,<v4,v7>1,<v4,v8>4,<v5,v6>4,<v5,v7>2,<v6,v10>4,<v7,v9>5,<v8,v9>2,<v9,v10>2}(注:边括号外的数据表示边上的权值),则G的关键路径的长度为?

3、对有n个顶点,e条边且使用邻接表存储的有向图进行广度优先遍历,其算法的时间复杂度是?

5 查找

5.1 顺序查找随堂测验

1、对线性表进行顺序查找,要求线性表的存储结构为 。
    A、散列存储
    B、顺序存储
    C、链接存储
    D、顺序存储或链接存储

2、用顺序查找方法在长度为n的线性表中进行查找,在等概率情况下,查找成功的平均查找长度为 。
    A、n
    B、n/2
    C、(n-1)/2
    D、(n+1)/2

5.2 二分法查找随堂测验

1、当n足够大时,在有序顺序表中进行折半查找,假设顺序表中每个元素的查找概率相同,则查找成功的平均查找长度为 。
    A、(n+1)/2
    B、n/2
    C、lg(n+1)-1
    D、lg(n+1)

2、对表长为n的有序表进行折半查找,其判定树的高度为 。
    A、lg(n+1)
    B、lg(n+1)-1
    C、lgn
    D、lg(n-1)

3、用n个键值构造一棵二叉排序树,其最低高度为 。
    A、n/2
    B、n
    C、lgn(向下取整)
    D、lgn+1(向下取整)

4、在含有n个节点的二叉排序树中查找一个关键码,最多进行次比较 。
    A、n/2
    B、lgn
    C、lgn+1
    D、n

5、长度为12的有序表采用顺序存储结构,采用折半查找技术,在等概率情况下,查找成功时的平均查找长度是 ,查找失败时的平均查找长度是 。
    A、37/12
    B、62/13
    C、39/12
    D、49/13

5.3 动态查找(一)随堂测验

1、按{10,20,30,100,40,25}的顺序构成平衡二叉树,其根结点是 。
    A、20
    B、30
    C、40
    D、25

5.4 动态查找(二)随堂测验

1、在一棵m阶B-树中删除一个关键码引起结点合并,则该结点原有 个关键码。
    A、1
    B、m/2(向上取整)
    C、m/2(向上取整)-1
    D、m/2(向上取整)+1

5.7 散列查找(二)随堂测验

1、平均查找长度与查找集合中记录个数n无关的查找方法是 。
    A、折半查找
    B、平衡二叉树的查找
    C、散列查找
    D、不存在

查找单元测验

1、对线性表进行顺序查找,要求线性表的存储结构为 。
    A、散列存储
    B、顺序存储
    C、链接存储
    D、顺序存储或链接存储

2、用顺序查找方法在长度为n的线性表中进行查找,在等概率情况下,查找成功的平均查找长度为 。
    A、n
    B、n/2
    C、(n-1)/2
    D、(n+1)/2

3、当n足够大时,在有序顺序表中进行折半查找,假设顺序表中每个元素的查找概率相同,则查找成功的平均查找长度为 。
    A、(n+1)/2
    B、n/2
    C、lg(n+1)-1
    D、lg(n+1)

4、对表长为n的有序表进行折半查找,其判定树的高度为 。
    A、lg(n+1)
    B、lg(n+1)-1
    C、lgn
    D、lg(n-1)

5、在含有n个节点的二叉排序树中查找一个关键码,最多进行次比较 。
    A、n/2
    B、lgn
    C、lgn+1
    D、n

6、按{10,20,30,100,40,25}的顺序构成平衡二叉树,其根结点是 。
    A、20
    B、30
    C、40
    D、25

7、平均查找长度与查找集合中记录个数n无关的查找方法是 。
    A、折半查找
    B、平衡二叉树的查找
    C、散列查找
    D、不存在

8、长度为12的有序表采用顺序存储结构,采用折半查找技术,在等概率情况下,查找成功时的平均查找长度是
    A、37/12
    B、62/13
    C、39/12
    D、49/13

9、长度为12的有序表采用顺序存储结构,采用折半查找技术,在等概率情况下,查找失败时的平均查找长度是
    A、37/12
    B、62/13
    C、39/12
    D、49/13

10、下面关于二分查找的叙述正确的是 ( )
    A、表必须有序,表可以顺序方式存储,也可以链表方式存储
    B、表必须有序,而且只能从小到大排列
    C、表必须有序且表中数据必须是整型,实型或字符型
    D、表必须有序,且表只能以顺序方式存储

11、当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度
    A、必定快
    B、不一定
    C、在大部分情况下要快
    D、取决于表递增还是递减

12、对线性表进行二分查找时,要求线性表必须( )
    A、以顺序方式存储
    B、以顺序方式存储,且数据元素有序
    C、以链接方式存储
    D、以链接方式存储,且数据元素有序

13、设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有( )个记录。
    A、1
    B、2
    C、3
    D、4

14、设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( )
    A、8
    B、3
    C、5
    D、9

15、假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?( )
    A、k-1次
    B、k次
    C、k+1次
    D、k(k+1)/2次

16、散列函数有一个共同的性质,即函数值应当以( )取其值域的每个值。
    A、最大概率
    B、最小概率
    C、平均概率
    D、同等概率

查找单元作业

1、已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个L中不存在的元素,则关键字的比较次数最多是?

2、给定一组关键字{20,30,50,52,60,68,70},给定创建一棵3阶B树的过程。

3、将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中,散列表的存储空间是一个下标从0开始的一维数组,散列函数为:H(key)=(key*3)MOD7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。 1.请画出所构造的散列表。 2.分别计算等概率情况下,查找成功和查找不成功的平均查找长度。

6 排序

6.1 排序的基本概念随堂测验

1、某内排序方法的稳定性是指 。
    A、该排序算法不允许有相同的关键字记录
    B、该排序算法允许有相同的关键字记录
    C、平均时间为0(n log n)的排序方法
    D、以上都不对

6.2 插入排序(一)随堂测验

1、直接插入排序用监视哨的作用是 。

6.4 交换排序——冒泡排序随堂测验

1、一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为 。
    A、(38,40,46,56,79,84)
    B、(40,38,46,79,56,84)
    C、(40,38,46,56,79,84)
    D、(40,38,46,84,56,79)

2、对于7 个元素的集合{1,2,3,4,5,6,7}进行快速排序,具有最小比较和交换次数的初始排列次序为_____。

6.5 交换排序——快速排序随堂测验

1、数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的 的两趟排序后的结果。
    A、选择排序
    B、冒泡排序
    C、插入排序
    D、堆排序

2、下列排序算法中,在每一趟都能选出一个元素放到其最终位置上,并且其时间性能受数据初始特性影响的是 。
    A、直接插入排序
    B、快速排序
    C、直接选择排序
    D、堆排序

3、下列排序算法中, 算法可能会出现下面情况:在最后一趟开始之前,所有元素都不在其最终的位置上。
    A、堆排序
    B、冒泡排序
    C、快速排序
    D、插入排序

6.7 归并排序随堂测验

1、下面给出的四种排序法中排序法 是不稳定性排序法。
    A、插入
    B、冒泡
    C、二路归并
    D、堆积

2、若需在O(nlogn)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是 。
    A、快速排序
    B、堆排序
    C、归并排序
    D、直接插入排序

3、在初始序列已基本有序(除去n 个元素中的某k 个元素后即呈有序,k<<n)的情况下,排序效率最高的算法是 。
    A、快速排序
    B、直接插入排序
    C、二路归并排序
    D、简单选择排序

4、排序趟数与序列的原始状态有关的排序方法是 排序法。
    A、插入
    B、选择
    C、冒泡
    D、归并

5、在下面的排序方法中,辅助空间为O(n)的是 。
    A、希尔排序
    B、堆排序
    C、选择排序
    D、归并排序

6、若不考虑基数排序,则在排序过程中,主要进行的两种基本操作是关键字的 和记录的 。

7、分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为有序的表,则最省时间的是 算法,最费时间的是 算法。

6.8 基数排序随堂测验

1、从平均时间性能而言,__________排序最佳。

2、不受待排序初始序列的影响,时间复杂度为O(n2)的排序算法是_____,在排序算法的最后一趟开始之前,所有元素都可能不在其最终位置上的排序算法是_____。

3、属于不稳定排序的有__________。(写出四个)

排序单元测试

1、某内排序方法的稳定性是指 。
    A、该排序算法不允许有相同的关键字记录
    B、该排序算法允许有相同的关键字记录
    C、平均时间为0(n log n)的排序方法
    D、以上都不对

2、一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为 。
    A、(38,40,46,56,79,84)
    B、(40,38,46,79,56,84)
    C、(40,38,46,56,79,84)
    D、(40,38,46,84,56,79)

3、数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的 的两趟排序后的结果。
    A、选择排序
    B、冒泡排序
    C、插入排序
    D、堆排序

4、下列排序算法中,在每一趟都能选出一个元素放到其最终位置上,并且其时间性能受数据初始特性影响的是 。
    A、直接插入排序
    B、快速排序
    C、直接选择排序
    D、堆排序

5、下列排序算法中, 算法可能会出现下面情况:在最后一趟开始之前,所有元素都不在其最终的位置上。
    A、堆排序
    B、冒泡排序
    C、快速排序
    D、插入排序

6、下面给出的四种排序法中排序法 是不稳定性排序法。
    A、插入
    B、冒泡
    C、二路归并
    D、堆积

7、若需在O(nlogn)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是 。
    A、快速排序
    B、堆排序
    C、归并排序
    D、直接插入排序

8、在初始序列已基本有序(除去n 个元素中的某k 个元素后即呈有序,k<<n)的情况下,排序效率最高的算法是 。
    A、快速排序
    B、直接插入排序
    C、二路归并排序
    D、简单选择排序

9、排序趟数与序列的原始状态有关的排序方法是 排序法。
    A、插入
    B、选择
    C、冒泡
    D、归并

10、在下面的排序方法中,辅助空间为O(n)的是 。
    A、希尔排序
    B、堆排序
    C、选择排序
    D、归并排序

11、下列关于排序的叙述中正确的是()
    A、稳定的排序方法优于不稳定的排序方法
    B、对同一线性表使用不同的排序方法进行排序得到的排序结果可能不同
    C、排序方法都是在顺序表上实现的,在链表中无法实现排序方法
    D、在顺序表中实现的排序方法在链表中也可以实现

12、对同一待排序序列分别进行折半插入排序和直接插入排序,两者之间可能的不同之处是()
    A、排序的总趟数
    B、元素的移动次数
    C、使用辅助空间的数量
    D、元素之间的比较次数

13、若对27个元素只进行3趟多路归并排序,则选取的归并路数最少是( )
    A、2
    B、3
    C、4
    D、5

14、已知序列 25,13,10,12,9,是大根堆,在序列尾部插入新元素18,将其再调整为大根堆,调整过程中元素之间进行比较次数是( )
    A、1
    B、2
    C、4
    D、5

15、对给定的关键字序列 110,119,007,911,114,120,122进行基数排序,第二趟分配收集后得到的关键字序列是( )
    A、007,110,119,114,911,120,122
    B、007,110,119,114,911,122,120
    C、007,110,911,114,119,120,122
    D、110,120,911,122,114,007,119

16、下列排序算法中,若将顺序存储更换为链式存储,则算法的时间效率会降低的是( )
    A、插入排序
    B、选择排序
    C、冒泡排序
    D、堆排序

17、将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是( )
    A、N
    B、2N-1
    C、2N
    D、N-1

18、在排序算法中每一项都与其它各项进行比较,计算出小于该项的项的个数,以确定该项的位置叫( )
    A、插入排序
    B、枚举排序
    C、选择排序
    D、交换排序

19、有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始堆为 ( )
    A、-1,4,8,9,20,7,15,7
    B、-1,7,15,7,4,8,20,9
    C、-1,4,7,8,20,15,7,9
    D、A,B,C均不对。

20、归并排序中,归并的趟数是( )。
    A、O(n)
    B、O(logn)
    C、O(nlogn)
    D、O(n*n)

21、对n 个记录的文件进行堆排序,最坏情况下的执行时间是多少?
    A、O(log2n)
    B、O(n)
    C、O(nlog2n)
    D、O(n*n)

22、快速排序方法在( )情况下最不利于发挥其长处。
    A、要排序的数据量太大
    B、要排序的数据中含有多个相同值
    C、要排序的数据个数为奇数
    D、要排序的数据已基本有序

23、对序列{15,9,7,8,20,-1,4,} 用希尔排序方法排序,经一趟后序列变为{15,-1,4,8,20,9,7},则该次采用的增量是 ( )
    A、1
    B、4
    C、3
    D、2

24、用直接插入排序方法对下面四个序列进行排序(由小到大),元素比较次数最少的是( )。
    A、94,32,40,90,80,46,21,69
    B、32,40,21,46,69,94,90,80
    C、21,32,46,40,80,69,90,94
    D、90,69,80,46,21,32,94,40

排序单元作业

1、给出关键字序列{4,5,1,2,6,3}的直接插入排序过程。

2、已知序列{503,87,512,61,908,170,897,275,653,462},采用二路归并排序法对该序列做升序排序时需要几趟排序?并给出每一趟的结果。

3、设关键字序列为{3,7,6,9,7,1,4,5,20},对其进行排序的最小交换次数是多少次?

数据结构与算法考试

数据结构与算法考试客观题部分

1、在一个单链表(节点的指针域用link标识)中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行( )。
    A、s->link=p; p->link=s;
    B、s->link=p->link; p->link=s;
    C、s->link=p->link; p=s;
    D、p->link=s; s->link=p;

2、下面关于线性表的叙述中,错误的是( )。
    A、线性表的顺序存储结构必须占用一片地址连续的存储单元
    B、线性表的链式存储结构不必占用一片地址连续的存储单元
    C、线性表的顺序存储结构可以随机存取任一数据元素
    D、线性表的链式存储结构可以随机存取任一数据元素

3、若一个串非空,子串的定位操作通常称为( )。
    A、串的长度
    B、原串的子串
    C、串的模式匹配
    D、串的连接

4、具有10个叶子结点的二叉树中有( )个度为2的结点。
    A、8
    B、9
    C、10
    D、12

5、队列通常采用两种存储结构是( )。
    A、顺序存储结构和链表存储结构
    B、散列方式和索引方式
    C、链表存储结构和数组
    D、线性存储结构和非线性存储结构

6、栈和队列的共同点是( )。
    A、都是先进后出
    B、都是先进先出
    C、只允许在端点处插入和删除元素
    D、没有共同点

7、设只包含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为( )。
    A、2^k
    B、2^(k+1)-1
    C、2^k+1
    D、2^(k-1)+1

8、设只包含根节点的二叉树的高度为1,则总共有( )种高度为5的完全二叉树。
    A、14
    B、15
    C、16
    D、17

9、在已知待排序记录已基本有序的前提下,效率最高的排序方法是( )。
    A、直接插入排序
    B、直接选择排序
    C、快速排序
    D、归并排序

10、比较次数与排序码的初始排列状态无关的排序方法是( )。
    A、直接插入排序
    B、直接选择排序
    C、快速排序
    D、冒泡排序

11、稳定的排序方法是( )。
    A、直接插入排序和快速排序
    B、堆排序和希尔排序
    C、直接选择排序和直接插入排序
    D、二分法插入排序和冒泡排序

12、一个具有n个顶点的连通无向图的生成树中至少有( )条边。
    A、n-1
    B、n
    C、n/2
    D、n+1

13、设散列表为HT[13],散列函数为h(key)=key%13。用线性探查法解决冲突,对下列关键码序列23,45,57,20,78,31,36造表。将36存储到散列中时需要探查( )次。
    A、1
    B、2
    C、3
    D、4

14、上题中构造的散列表在等概率情况下,搜索成功的平均搜索长度是( )。
    A、7/13
    B、1
    C、11/7
    D、12/7

15、图的广度优先搜索类似于树的( )次序遍历。
    A、先根
    B、中根
    C、后根
    D、层

数据结构与算法主观题部分

1、已知二叉树的后序和中序序列如下,画出该二叉树。 后序序列:DEABFCR 中序序列:DAERBCF

2、有7个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点生成一棵哈夫曼树,画出相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)。

3、设图G=(V,E),V={1,2,3,4,5,6},E={<1,2>,<1,3>,<2,5>,<3,6>,<6,5>,<5,4>,<6,4>}。请写出图G中顶点的所有拓扑序列。

4、假定一组记录的排序码为(46,79,56,38,40,84,50,42),利用堆排序方法画出初始大顶堆(以树状表示)。

5、已知一个图的顶点集V和边集G分别为: V={0,1,2,3,4,5,6,7}; G={(0,1)3,(0,3)5,(0,5)18,(1,3)7,(1,4)6,(2,4)10,(2,7)20,(3,5)15,(3,6)12,(4,6)8,(4,7)12}; 按照普里姆算法从顶点2出发得到最小生成树,试写出在最小生成树中依此得到的各条边。

6、设一组记录的关键字为{50,86,72,41,45,93,57,46},按不减序排序。分别给出快速排序,二路归并排序和希尔排序(增量d1=3)的第一趟排序结果。

7、设输入的关键字序列为:22,41,53,33,46,30,13,01,67, Hash函数为:H(key)=key% 11。HASH表长度为11。试用线性探测法解决冲突,将各关键字按输入顺序填入Hash表中。画出相应的散列表,并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。