1、第一章 绪论一、问答题 1. 什么是数据结构？ 2. 叙述四类基本数据结构的名称与含义。3. 叙述算法的定义与特性。4. 叙述算法的时间复杂度。5. 叙述数据类型的概念。 6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么？9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。 二、判断题（在各题后填写“”或“”） 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ）2. 算法就是程序。（ ） 3. 在高级语言（如 C 或 PASCAL）中，指针类型是原子类型。（ ）三、计算下列程序
2、段中 X=X+1 的语句频度 for(i=1;inext=S; （2 ） P-next= P-next-next; （3 ） P-next= S-next; （4 ） S-next= P-next; （5 ） S-next= L; （6 ） S-next= NULL; （7 ） Q= P; （8 ） while(P-next!=Q) P=P-next; （9 ） while(P-next!=NULL) P=P-next; （10 ）P= Q; （ 11）P= L; （12）L= S; （13 ）L= P; 2.4 已知线性表 L 递增有序。试写一算法，将 X 插入到 L 的适当位置上，以保持线
3、性表 L 的有序性。 Status Insert_SqList(SqList va.length+; for(i=va.length-1;va.elemixi-) va.elemi+1=va.elemi; va.elemi+1=x; return OK; /Insert_SqList2.5 写一算法，从顺序表中删除自第 i 个元素开始的 k 个元素。 2.6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于 mink 且小于 maxk 的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink 和 maxk 是给定的两个参变量，它
4、们的值为任意的整数）2.7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2., an）逆置为（an, an-1,., a1）。 （1 ） 以顺序表作存储结构。 （2 ） 以单链表作存储结构。2.8 假设两个按元素值递增有序排列的线性表 A 和 B，均以单链表作为存储结构，请编写算法，将 A 表和 B 表归并成一个按元素值递减有序的排列的线性表 C，并要求利用原表（即 A 表和 B 表的）结点空间存放表 C. 2.9 假设有一个循环链表的长度大于 1，且表中既无头结点也无头指针。已知 s 为指向链表某个结点的指针，试编写算法在链表中删除指针 s 所指结点
5、的前趋结点。2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。2.11 设线性表 A=(a1, a2,am)，B=(b1, b2,bn)，试写一个按下列规则合并 A、B 为线性表C 的算法，使得： C= (a1, b1,am, bm, bm+1, ,bn) 当 mn 时； 或者C= (a1, b1,an, bn, an+1, ,am) 当 mn 时。 线性表 A、B、 C 均以单链表作为存储结构，且 C 表利用 A
6、表和 B 表中的结点空间构成。注意：单链表的长度值 m 和 n 均未显式存储。 2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 data 域存放一个二进制位。并在此链表上实现对二进制数加 1 的运算 。2.14 设多项式 P(x)采用课本中所述链接方法存储。写一算法，对给定的 x 值，求 P(x)的值。第三章 栈和队列1. 按图 3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： 如进站的车厢序列为 1
7、23，则可能得到的出站车厢序列是什么？ 如进站的车厢序列为 123456，能否得到 435612 和 135426 的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。2. 设队列中有 A、B 、C、D、 E 这 5 个元素，其中队首元素为 A。如果对这个队列重复执行下列 4 步操作： （1 ） 输出队首元素； （2 ） 把队首元素值插入到队尾； （3 ） 删除队首元素； （4） 再次删除队首元素。 直到队列成为空队列为止，则是否可能得到输出序列： （A）A、 C、E、C、C （B） A、C、E （C） A、C 、E、C、C、C （D） A、C、E、C3. 给出栈
8、的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4. 按照四则运算加、减、乘、除和幂运算（）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： AB5. 试写一个算法，判断依次读入的一个以 为结束符的字母序列，是否为形如序列 1 n=0; while(!EmptyStack(S) n+; Pop( for(i=1; i=n; i+) Push( （2 ） void proc_2(Stack S, int e) Stack T; int d; InitStack( while(!EmptyStack(S) Pop( if (d!=e) Push( whil
9、e(!EmptyStack(T) Pop( Push( （3 ） void proc_3(Queue *Q) Stack S; int d;InitStack( while(!EmptyQueue(*Q) DeleteQueue(Q, Push( while(!EmptyStack(S) Pop( EnterQueue(Q，d) 第四章 串1. 设 s=I AM A STUDENT, t=GOOD, q=WORKER。给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,A,4); St
10、rReplace(s,STUDENT,q); StrCat(StrCat(sub1,t), StrCat(sub2,q);2. 编写算法，实现串的基本操作 StrReplace(S,T,V)。3. 假设以块链结构表示串，块的大小为 1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)；SubString(Sub,S,pos,len)。4 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。5 已知：S=
11、”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将 S 转换为T. 6 S 和 T 是用结点大小为 1 的单链表存储的两个串，设计一个算法将串 S 中首次与 T匹配的子串逆置。7 S 是用结点大小为 4 的单链表存储的串 ,分别编写算法在第 k 个字符后插入串 T，及从第 k 个字符删除 len 个字符。 以下算法用定长顺序串： 8 写下列算法： （1 ） 将顺序串 r 中所有值为 ch1 的字符换成 ch2 的字符。（2 ） 将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。（ 3） 从顺序串 r 中删除其值等于 ch 的所有字符。（ 4） 从顺序串 r1 中
12、第 index 个字符起求出首次与串 r2 相同的子串的起始位置。（ 5） 从顺序串 r 中删除所有与串 r1 相同的子串。 9 写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。10 写算法，实现顺序串的基本操作 StrCompare(s,t)。11 写算法，实现顺序串的基本操作 StrReplace(&s,t,v)。 第五章 数组和广义表1 假设有 6 行 8 列的二维数组 A，每个元素占用 6 个字节，存储器按字节编址。已知 A的基地址为 1000，计算： （1 ） 数组 A 共占用多少字节；（2 ） 数组 A 的最后一个元素的地址；（ 3） 按行存
13、储时，元素 A36 的地址； （4 ） 按列存储时，元素 A36 的地址。第六章 数和二叉树1试分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。2对题 1 所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3已知一棵度为 k 的树中有 n1 个度为 1 的结点，n2 个度为 2 的结点，nk 个度为 k的结点，则该树中有多少个叶子结点并证明之。4.假设一棵二叉树的先序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK，请画出该二叉树。5. 已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有多少个？6. 给出满足下列条件的所有二叉树： a)
14、前序和中序相同b) 中序和后序相同 c) 前序和后序相同 7 n 个结点的 K 叉树，若用具有 k 个 child 域的等长链结点存储树的一个结点，则空的Child 域有多少个？8画出与下列已知序列对应的树： 树的先根次序访问序列为 GFKDAIEBCHJ；树的后根次序访问序列为 DIAEKFCJHBG。 9 假设用于通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03 ，0.21，0.10 请为这 8 个字母设计哈夫曼编码。10已知二叉树采用二叉链表存放, 要求返回二叉树 T 的后序序列中的第一个结点的指针 ,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树： 12 已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13 编写递归算法：对于二叉树中每一个元素值为 x 的结点，删去以它为根的子树，并释
