数据结构实验考试题
1. 已知线性表A,B,C是递增有序的线性表。要求对A表作如下运算：删去那些既在B表
中出现又在C表中出现的元素。A,B,C以顺序表存储。
2. 假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构。请编写程
序将A表和B表归并成一个按元素递减有序排列的线性表C,并要求利用原表结点空间存放C表。
3. 求以递增序排列的两个线性表A和B的交集，将结果存于新表C中。要求C中元素仍
然以递增序排列，并且C中没有重复的元素。以顺序结构实现此算法。
4. 设A=(a1, ... ,am)和B=(b1,...,bn)均为有序线性表，A' 和 B' 分别为A、B中除去最大共
同前缀后的子表。若A' = B' = 空，则A=B；若A' = 空表，B'≠空表，或者两者均不空且A'首元小于B'首元，则A
5. 单链表中的元素以递增序存放,写一算法,删除表中所有值大于mink且小于maxk的元素
(如果这样的元素存在).
6. 假设以循环链表作稀疏多项式的存储结构，编写求两个稀疏多项式乘积的算法。要求：
不破坏原来的多项式链表。
7. 设两个栈共享向量空间v(1:m),它们的栈底分别在向量的两端，进栈的每个元素只占用
一个分量。写出这两个栈公用的栈操作算法：push(i,x), pop(i)和top(i,x)。其中i=0或1，分别代表两个不同的栈。 8. Ackerman函数的非递归解法
akm(m,n) = n + 1 (当m = 0时)
akm(m-1,1) (当m <> 0 且 n = 0时)
akm(m-1,akm(m,n-1)) (当m<>0 且 n<>0时)
9. 求一个广义表的深度*广义表的深度即是括号的最大层数。通过记录一个表中所出现的
配对括号的层数，就可以求出广义表的深度。
10. 具有头结点的两个单链表的链接。已知：头结点的数据段中放的是链表长度。两个链表
的链接是指将一个链表的第一个元素链接到另一个链表的尾部。要求：算法必须有最小的时间代价
? 以数组储存的队列，设置rear和quelen两个变量分别表示队尾元素位置和队列长度。
写出入/出队列的算法。
? 以数组存储的循环队列，编写能充分利用数组中每个元素的入/出队列算法。此题需要
设立一个标志，以指示当rear = front时队列是空还是满。 ? 求矩阵中所有的马鞍点。若矩阵 A[0:m-1,0:n-1]中的某个元素A[i,j]是第i行中的最小值，
同时右又是第j列中的最大值，则它就是马鞍点。
? 用堆栈实现判断一个算术表达式中括号是否配对的算法。假设一个算术表达式中可以包
括(),[],{}三类括号，且这三种括号可以任意嵌套使用。 ? 试编写一个将百分制转换成五分制的算法，要求其时间性能尽可能地高。假定学生成绩
的分布情况如下：
分数 0-59 60-69 70-79 80-89 90-100 比例 0.05 0.15 0.40 0.30 0.10
? 设线性表存于数组array中，且递增有序。将一个新元素x插入到线性表中，并保持排
序状态。
? 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表
中某个结点的指针，编写在链表中删除s所指结点的前驱结点的算法。
? 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法。要求利用原结点空间
并释放多余结点。
? 已知单链表表示的线性表中含有三类字符数据元素，一类为数字，一类为字母，一类为
其他符号。试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
? 试设计一个算法，将数组A(0:n-1)中的元素循环右移k位，并要求只用一个元素大小的
附加存储，元素移动或交换的次数为O(n)。
? 用一维数组做存储结构，就地逆置一线性表。如：(a1,a2,...an)逆置后为(an,an-1,...,a1) ? 设有一个双链表，每个结点中除了有pre,data和next三个域外，还有一个访问 频度域
freq，在链表起用之前，所有的freq = 0。每当在链表进行一次LOCATE(l,x) 运算时，令元素值等于x的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。
? 背包问题：假设一个背包可以装入总重量为T的物品，现在有n件物品，其重量分别
为： w1,w2,...,wn。求{wx1,wx2,...,wxn}包含于{w1,w2,...,wn}使得wx1+wx2 + ... + wxn = T。（wi <> wj, i<>j; wxi <> wxj, i <>j） ? （1）若n=1,则当w1 = T时有解；（2）若n>1,则此题化为：求T' = T - wj, 物品重量为
w1,w2,... w(j-1),w(j+1),...,wn时的背包问题。j = 1,2,...,n 如此递归，可解。 ? 写出求递归函数f(n)的非递归算法： f(n) = n+1 (当n=0) f(n) =n*f((int)(n/2)) (当n>0)
? 假定用两个一维数组L(0:n-1)和R(0:n-1)作为有n个结点的二叉树的存储结构，L[i]和
R[i]分别指示结点i的左孩子和右孩子，-1 表示空。 （1）判别结点u是否为结点v的子孙；
（2）先由L和R建立一维数组T(0:n-1),使T中第i个元素(i=0,2,...,n-1)
指示结点i的双亲，然后写判别结点u是否是v的子孙的算法。
? 通过键盘输入的扩充二叉树的前序遍历序列, 建立二叉树，然后按中序和后序输出此
树，并求该树的叶结点个数和度数为2的结点个数。假设二叉树结点的数据为char型，其中扩充结点用'*'号表示。
? 在一棵以二叉链表存储的二叉树中，求在前序序列中排在第k位的结点假设表达式由单
字母变量和双目运算符构成，写一个算法，判断表达式是否为正确的后缀表达式。如果是，将其转化为前缀表达式。
? 假设二叉树中左分支的标号为\右分支的标号为\，并对二叉树增设一个头结点，令
根结点为其右孩子。则：从头结点到树中任意一结点所经分支的序列为一个二进制序列，将这个二进制序列的值作为该结点对应的值。 ? 已知一棵非空二叉树以顺序结构存储，变量i为树中某结点在顺序存储结构中的下标值，
写一个尽可能简单的算法，求出于该结点对应的值。如： (a) 0/ \\1 (b) (c) 0/ \\1 (e) (g) 0/
(h) h对应的二进制序列为1110,即十进制的14。
? 假设二叉树T中至多有一个结点的数据域为x,编写算法拆去以该结点为根的子树，使
原树分为两棵。例如x = 9,二叉树的变化如下： 13 /\\ 3 16 / \\ \\ 2 9 27 / / \\ 4 6 11
拆开后：
13 /\\
3 16 / \\ 2 27 / 4 9 / \\ 6 11
? 用递归的方法复制一棵二叉树，假设二叉树以二叉链表存储。 ? 设计一个算法输出已知二叉树中所有叶子结点的值
? 已知一棵二叉树以二叉链表为存储结构，编写如下算法：对于树中每一个元素值为x
的结点，删去以它为根的子树，并释放相应的空间。
? 编写算法查找二叉树中数据域值为X的结点（假定各结点的数据域值各不相同），并打
印出X所有祖先的数据域值。
? 编写判断两个二叉树是否相等的算法。若T1与T2是等价的，则要么T1与T2是空树，
要么T1和T2的值相同并且T1、T2的左右子树分别相等。 ? 编写判断两个二叉树是否相似的算法。若T1与T2是相似的，则要么T1与T2是空树，
要么T1和T2都不是空树并且T1、T2的左右子树分别相似。假设树是以二叉链表形式存储的。
? 写一算法,判断一棵二叉树是否是完全二叉树。 ? 对二叉树进行层次遍历
? 求一棵二叉树中每个层次的结点数 ? 编写一个算法，输出以二叉树表示的算术表达式。要求：在需要加括号的地方加上括号。 ? 假设以二叉链表存储的二叉树中，每个结点所含的数据元素均为单字母，编写算法，按
树状打印二叉树。如：
a / \\ b c \\ / d e \\
f 打印为：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
c f e a d b
一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中。编写非递归算法对该树进行前序遍历。
以二叉链表为二叉树的存储结构，写出求某个结点的父结点的算法。 编写算法交换二叉树中所有结点的左、右子树。
一棵二叉树的前序序列和中序序列分别存在两个数组中，编写算法，建立以二叉链表为结点的该二叉树。
一棵二叉树的后序序列和中序序列分别存在两个数组中，编写算法，建立以二叉链表为结点的该二叉树。 huffman算法
图解最小生成树算法 无向图邻接表生成算法
从一个顶点到其它顶点的最短路径算法 图的各个顶点最短路径 图的深度遍历 图的广度遍历 顺序查找算法 二分查找算法 冒泡排序算法 快速排序算法 希尔排序算法 直接插入排序
基数、归并排序算法