www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

单项选择题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. 选择排序 B. 希尔排序

C. 归并排序 D. 快速排序 单项选择题2、

不定长文件是指（ ）

A. 文件的长度不固定 B. 记录的长度不固定 C. 字段的长度不固定 D. 关键字项的长度不固定 单项选择题3、

如下陈述中正确的是（ ）

A. 串是一种特殊的线性表 B. 串的长度必须大于零 C. 串中元素只能是字母 D. 空串就是空白串 单项选择题4、

将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ） A. O（1） B. O（n） C. O（m） D. O（m+n） 单项选择题5、

设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）

A. front=front+1 B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m

单项选择题6、计算机算法必须具备输入、输出和 等5个特性 A. 易读性、稳定性和安全性 B. 确定性、有穷性和稳定性 C. 可行性、可移植性和可扩充性 D. 可行性、确定性和有穷性

单项选择题7、有8个结点的无向图最多有 条边 A. 112 B. 56 C. 28 D. 14

单项选择题8、不含任何结点的空树 A. 是一棵二叉树 B. 是一棵树

C. 是一棵树也是一棵二叉树 D. 既不是树也不是二叉树

单项选择题9、一棵深度为6的满二叉树有 个分支结点 A. 30 B. 31 C. 32 D. 33

单项选择题10、把一棵树转换为二叉树后，这棵二叉树的形态是 A. 唯一的 B. 有多种

C. 有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

单项选择题11、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是: A. O(log2n) B. O(1) C. O(n) D. O(nlog2n)

单项选择题12、若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ） A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入

单项选择题13、设哈希表长m=14,哈希函数H(key)=key MOD 11。表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为: A. 3 B. 5 C. 8 D. 9

单项选择题14、设一棵完全二叉树有300个结点，则共有 个叶子结点 A. 150 B. 152 C. 154 D. 156

单项选择题15、由３个结点所构成的二叉树有 种形态. A. 2 B. 3 C. 4 D. 5

单项选择题16、设有两个串p和q，求q在p中首次出现的位置的运算称作： A. 连接 B. 模式匹配 C. 求子串 D. 求串长

单项选择题17、

栈中元素的进出原则是: A. 先进先出 B. 后进先出 C. 栈空则进 D. 栈满则出

单项选择题18、链表是一种采用 存储结构存储的线性表. A. 顺序 B. 星式 C. 链式 D. 网状

单项选择题19、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： A. 存储结构 B. 顺序存储结构 C. 逻辑结构 D. 链式存储

单项选择题20、判断一个循环队列Q（最多n个元素）为满的条件是: A. Q->front==(Q->rear+1)%n B. Q->rear==Q->front+1 C. Q->front==(Q->rear-1)%n

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

D. Q->rear==Q->front

单项选择题21、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是: A. p=p->next

B. p=p->next->next C. p->next=p

D. p->next=p->next->next

单项选择题22、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是:

A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;

B. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; C. q->next=p->next;q->prior=p;p->next=q;p->next=q;

D. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next; 单项选择题23、

在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A. 4

B. 5 C. 6 D. 7

单项选择题24、 算法指的是（ ） A. 计算机程序

B. 解决问题的计算方法

C. 排序算法 D. 解决问题的有限运算序列 单项选择题25、

在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A. n*n－e B. n*n－2e C. e D. 2e 单项选择题26、

线性表采用链式存储时，结点的存储地址（ ） A. 必须是不连续的 B. 连续与否均可 C. 必须是连续的

D. 和头结点的存储地址相连续

多项选择题 27、抽象数据类型的组成部分分别为: A. 数据对象 B. 存储结构 C. 数据关系 D. 基本操作

多项选择题 28、不具有线性结构的数据结构是： A. 图 B. 栈 C. 广义表 D. 树

多项选择题 29、算法分析的两个主要方面是( ) A. 正确性 B. 简单性 C. 空间复杂度 D. 时间复杂度

判断题30、树在实际应用中采用多种不同的形式表示和存储 A.√ B.×

判断题31、 完全二叉树一定是满二叉树 A.√ B.×

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

判断题32、在完全二叉树中，叶节点个数比分支节点个数多1 A.√ B.×

判断题33、 任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。 A.√ B.×

判断题34、栈和队列逻辑上都是线性表 A.√ B.×

判断题35、 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 A.√ B.×

判断题36、 若用链表来表示一个线性表，则表中元素的地址一定是连续的。 A.√ B.×

判断题37、链表的每个结点中都恰好包含一个指针 A.√ B.×

判断题38、如果将所有中国人按照生日来排序，则使用哈希排序算法最快 A.√ B.×

判断题39、折半查找只适用于有序表，包括有序的顺序表和链表 A.√ B.×

判断题40、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。 A.√ B.×

判断题41、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。 A.√ B.×

判断题42、 一般树和二叉树的结点数都可以为0; A.√ B.×

判断题43、 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123 A.√ B.×

判断题44、 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑\溢出\情况。 A.√ B.×

判断题45、 一棵有124个结点的完全二叉树，其叶结点个数是确定的 A.√ B.×

填空题 46、 中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。

填空题 47、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间.

填空题 48、 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。 填空题 49、

快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。 填空题 50、

设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

应用题 51、

一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

应用题 52、写出用直接插入排序将关键字序列{54,23,89,48,64,50,25,90,34}排序过程的每一趟结果。 应用题 53、

阅读以下二叉树操作算法，指出该算法的功能。

Template void BinTree ：： unknown (BinTreeNode*t) {

BinTreeNode< Type> *p =t, *temp; if (p!=NULL) {

temp = p→leftchild;

p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild); } }

该算法的功能是：________________________________

应用题 54、 已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。 应用题 55、

已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的每一次划分结果。

应用题 56、设待排序序列为{10,18,4,3,6,12,1,9,15,8}请写出希尔排序每一趟的结果。增量序列为5，3，2，1。

应用题 57、写出下列程序的时间复杂度 s=0;

for i=0; i

应用题 58、设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有

① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？ 应用题 59、

写出下列程序的时间复杂度 for(i=0; i

综合分析题 60、

设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 综合分析题 61、

设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。 单项选择题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. 选择排序