1、一、选择题（1）数据结构通常是研究数据的（ A ）及它们之间的相互联系。A. 存储结构和逻辑结构 B. 存储和抽象 C. 联系和抽象 D. 联系与逻辑（2）在逻辑上可以把数据结构分成：（ C ） 。A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构（3）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ C ） 。A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结（4）算法分析的两个主要方面是（ A ） 。A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序
2、复杂性（5）下列时间复杂度中最坏的是（ D ） 。A. O（1） B. O（ n） C. O（log 2n） D. O（n 2）（6）等概率情况下，在有 n 个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ C ） 。An B(n-1)/2 C n/2 D(n+1)/2（ 7） 设 有 编 号 为 1， 2， 3， 4的 四 辆 列 车 ， 顺 序 进 入 一 个 栈 结 构 的 站 台 ， 下 列 不 可 能的 出 站 顺 序 为 ( D )A 1234 B 1243 C 1324 D 1423（ 8） 如 果 以 链 表 作 为 栈 的 存 储 结 构 ， 则 出 栈 操 作 时
3、（ B ）A 必 须 判 别 栈 是 否 满 B 必 须 判 别 栈 是 否 空C 必 须 判 别 栈 元 素 类 型 D 队 栈 可 不 做 任 何 判 别（ 9） 链 栈 与 顺 序 栈 相 比 ， 有 一 个 比 较 明 显 的 优 点 是 （ B ） 。A 插 入 操 作 更 加 方 便 B 通 常 不 会 出 现 栈 满 的 情 况 。C 不 会 出 现 栈 空 的 情 况 D 删 除 操 作 根 加 方 便（ 10） 插 入 和 删 除 只 能 在 一 端 进 行 的 线 性 表 ， 称 为 ( C )。A 队 列 B 循 环 队 列 C 栈 D 循 环 栈 （ 11） 若 进 队
4、 的 序 列 为 ： A， B， C， D， 则 出 队 的 序 列 是 （ C ） 。A B， C， D， A B A， C， B， D C A， B， C， D D C， B， D， A（12）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为 3和 0， 当从 队 列 中 删 除 一 个 元 素 ， 再 加 入 两 个 元 素 后 ， front和rear的值分别为( B )。A 5和 1 B 4和 2 C 2和 4 D 1和 5（ 13） S=“morning“， 执 行 求 子 串 函 数 SubStr(S,2,2)后 的 结 果 为 ( B )。A “mo“
5、 B “or“ C “in“ D “ng“（ 14） S1=“good“， S2=“morning“， 执 行 串 连 接 函 数 ConcatStr(S1,S2)后 的 结 果 为( A )。A “goodmorning“ B “good morning“C “GOODMORNING“ D “GOOD MORNING“（ 15） S1=“good“， S2=“morning“， 执 行 函 数 SubStr(S2,4,LenStr(S1)后 的 结 果 为( B )。A “good“ B “ning“C “go“ D “morn“（ 16） 设 串 S1=“ABCDEFG“， S2=“PQR
6、ST“ ,则 ConcatStr(SubStr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)的 结 果 串 为 ( D )。A BCDEF B BCDEFG C BCPQRST D. BCDEFEF(17)已知二维数组A610，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a35的存储地址是1000，则a00的存储地址是（ B ） 。A 872 B 860 C 868 D 864（18）在一棵具有五层的满二叉树中，结点的总数为（ B ）A16 B31 C32 D33（19）具有 64 个结点的完全二叉树的深度为（ C ）A5 B6 C7（20）具有 n
7、（n1）个结点的完全二叉树中，结点 i（2in）的左孩子结点是（ D ） 。A2i B2i+1 C2i-1 D不存在（若 2iprior-next=p-next 。（5） A+B/C-D*E 的后缀表达式是： ABC/+DE*- 。（6） 解决顺序队列“假溢出”的方法是采用 循环队列 。（7） 循环队列的队首指针为 front，队尾指针为 rear，则队空的条件为 front = rear 。（ 8） 设 循 环 队 列 的 头 指 针 front指 向 队 首 元 素 ， 尾 指 针 rear指 向 队 尾 元 素 后 的 一个 空 闲 元 素 ， 队 列 的 最 大 空 间 为 MAXLE
8、N， 则 队 满 标 志 为 ： front=(rear+1)%MAXLEN 。（ 9） 设循环队列的容量为40（序号从0到39） ，现经过一系列的入队和出队运算后，有 front=11，rear=19，则循环队列中还有 8 个元素。 （L= (Nrearfront)%N=（401911）% 40=8）（ 10） 设 S=“My Music“， 则 LenStr(s)= _ 8 。（ 11） 两 个 字 符 串 分 别 为 ： S1=“Today is“， S2=“30 July,2005“,ConcatStr(S1,S2)的 结 果 是 ： Today is 30 July,2005 。（
9、12） 求 子 串 函 数 SubStr(“Today is 30 July,2005“,13,4)的 结 果 是 ： July 。（ 13） 在 串 的 运 算 中 ， EqualStr(aaa,aab)的 返 回 值 为 data= x ; p=head-next;while (p!=NULL) if (p=NULL)coutnext=p-next_;_ p-next=s _;(2)假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针 rear，试填空完成向循环队列中插入一个元素为 x 的结点的函数。typedef struct queuenode / 定义队列的存储结构 int
10、data;struct queuenode *next;QueueNode;InQueue(QueueNode *rear,int x) / 向队列插入元素为 x 的函数 QueueNode *rear;QueueNode *head,*s;s= new QueueNode ;s-data= x ;if(rear=NULL) / 循环队列为空，则建立一个结点的循环队列 rear=s; rear-next; else head= rear-next ; / 循环队列非空，则将 s 插到后面rear-next= s ;rear=s;rear-next =head;（3）下面程序是把两个串 r1 和
11、 r2 首尾相连的程序，即： r1=r1+r2，试完成程序填空。typedef Struct char vecMAXLEN; / 定义合并后串的最大长度int len; / len 为串的长度St ;void ConcatStr(Str *r1,Str *r2) / 字符串连接函数 int i;coutvecvec;if(r1-len+r2-len MAXLEN )coutlen ;i+) / 把 r2 连接到 r1r1-vec r1-len+i =r2-veci; r1-vecr1-len+i= 0 ; / 添上字符串结束标记r1-len= r1-len+r2-len ; / 修改新串长度(
12、4)下面算法是判断字符串是否为回文（即正读和倒读相同） ，试完成程序填空。#include “stdio.h“typedef struct char vecMAXLEN;int len;str;void Palindrome (str s) int i=0;ing j= s.len-1 ;while ( j-i=1 ) if ( s.veci= s.vecj )i+; j- ;continue / (或 j=j+1 )else break;if ( j-i=1 )cout=high+1;j-)Rj+1= R j ; / 元素后移Rhigh=R0; / 插入四、应用题（1）已知一棵二叉树的后序遍
13、历和中序遍历的序列分别为：ACDBGIHFE 和 ABCDEFGHI。请画出该二叉树，并写出它的前序遍历的序列。解：恢复的二叉树为： 其前序遍历的序列为：E B A D C F H G I（2） 把下列一般树转换为二叉树 解： （3）把下列森林转换为二叉树 BCHDDFGEIA1243 56 78ABFE G H IJC DACB DE KI JHFGABCH DDFGEIJ12468 8D537解：（4）把下列二叉树还原为森林解：还原后的二叉树为： （5）假设用于通信的电文仅由 A、B、C、D、E、F、G 8 个字母组成，字母在电文中出现的频率分别为 7，19，2，6，32，3，21，10。
14、试为这 8 个字母设计哈夫曼编码。解：以权值：2、3、6、7、10、19、21、32 构造哈夫曼树：（左子为 0，右子为 1。 ）ADBICHF GEKABC HDDFGE IJAB C HDDFGEI651911281740D21 3260D10000D02 3D7 10D0 0000111111 0 1字母编号 对应编码 出现频率A 1010 7B 00 19C 10000 2D 1001 6E 11 32D 10001 3E 01 21F 1011 10（6）有向图如下图所示，画出邻接矩阵和邻接表解：邻接矩阵1 2 3 4 5 0101054邻接表1 2 3 5 2 4 3 5 4 1 5 4 （7）已知一个无向图有 6 个结点，9 条边，这 9 条边依次为(0,1)，(0,2)，(0,4)，(0,5)，(1,2)，(2,3)，(2,4)，(3,4)，(4,5)。试画出该无向图，并从顶点 0 出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。解：
