数据结构与程序设计复习 第一章数据结构概论 1.1判断下列叙述的对错。如果正确,在题前打“√”,否则打“x” (1)数据元素是数据的最小单位 (2)数据结构是数据对象与对象中数据元素之间关系的集合。 (3)数据结构是具有结构的数据对象 (4)数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要建立的。 (5)算法和程序原则上没有区别,在讨论数据结构时二者是通用的。 12判断下列叙述的对错。如果正确,在题前打“√”,否则打“×” (1)所谓数据的逻辑结构是指数据元素之间的逻辑关系 (2)同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据 项的个数都相等 (3)数据的逻辑结构与数据元素本身的内容和形式无关。 (4)数据结构是指相互之间存在一种或多种关系的数据元素的全体 (5)从逻辑关系上讲,数据结构主要分为两大类:线性结构和非线性结构 1.3填空题 算法是一个有穷的指令集,它为解决某一特定任务规定了一个运算序列。它应当具有 输入、输出、(①)、有穷性和可执行性等特性 算法效率的度量分为(②)和(③)。(②)主要通过在算法的某些部位插装时间函数 来测定算法完成某一规定功能所需的时间。而(③)不实际运行算法,它是分析算法中语 句的执行次数来度量算法的时间复杂性。 程序所需的存储空间包含两个部分(④)和(⑤)。(④)空间的大小与输入输出数据 的个数多少,数值大小无关;(⑤)空间主要包括其大小与问题规模有关的成分变量所占 空间,引用变量所占空间,以及递归栈所用的空间,还有在算法运行过程中动态分配和回 收的空间 14设n为正整数,分析下列各程序段中加下划线的语句的执行次数 (1)for int i=1; i<=n; 1++) for( intj=1;j<=n;j++) c[U]=0.0; for( int k=1; k<=n; k++) cin=cill+allk blklli: (2)x=0;y=0; for( int i=1;i<=n;i++ for( intj=1:j<=;j++) for( int k=l; k <=j:k++) 1.5试计算以下求和程序中所有语句的总执行次数。 float sum( float a[, int n)(
数据结构与程序设计复习 1 第一章 数据结构概论 1.1 判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 (1) 数据元素是数据的最小单位。 (2) 数据结构是数据对象与对象中数据元素之间关系的集合。 (3) 数据结构是具有结构的数据对象。 (4) 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 (5) 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。 1.2 判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 (1) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。 (2) 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据 项的个数都相等。 (3) 数据的逻辑结构与数据元素本身的内容和形式无关。 (4) 数据结构是指相互之间存在一种或多种关系的数据元素的全体。 (5) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。 1.3 填空题 算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有 输入、输出、( ① )、有穷性和可执行性等特性。 算法效率的度量分为( ② )和( ③ )。( ② )主要通过在算法的某些部位插装时间函数 来测定算法完成某一规定功能所需的时间。而( ③ )不实际运行算法，它是分析算法中语 句的执行次数来度量算法的时间复杂性。 程序所需的存储空间包含两个部分( ④ )和( ⑤ )。( ④ )空间的大小与输入输出数据 的个数多少，数值大小无关；( ⑤ )空间主要包括其大小与问题规模有关的成分变量所占 空间，引用变量所占空间，以及递归栈所用的空间，还有在算法运行过程中动态分配和回 收的空间。 1.4 设 n 为正整数, 分析下列各程序段中加下划线的语句的执行次数。 (1) for ( int i = 1; i <= n; i++ ) for ( int j = 1; j <= n; j++ ) { c[i][j]=0.0; for ( int k = 1; k <= n; k++ ) c[i][j] = c[i][j] + a[i][k] * b[k][j]; } (2) x = 0; y = 0; for ( int i = 1; i <= n; i++ ) for ( int j = 1; j <= i; j++ ) for ( int k = 1; k <= j; k++ ) x = x + y; 1.5 试计算以下求和程序中所有语句的总执行次数。 float sum( float a[ ], int n ) {
数据结构与程序设计复习 for int 1=0; i <n; 1++) S+=aj; return s; 6试用大O表示法给出下面程序的时间复杂性 void out( float x[[, int m, int)i for int i=0; i<m; i++)& sum[i]=0.0: for intj=0; j<n;j++) i=xill for int 1=0; i <m; 1++) cout <<"Line: "<<1<<": <<sum(i]<< endl 第二章数组 21判断下列叙述的对错。如果正确,在题前打“√”,否则打“ (1)线性表的逻辑顺序与物理顺序总是一致的 (2)线性表的顺序存储表示优于链式存储表示。 (3)线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。 (4)二维数组是其数组元素为线性表的线性表 5)每种数据结构都应具备三种基本运算:插入、删除和搜索。 2.2线性结构可用顺序表或链表存储。试问: (1)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数 也可能自动改变、在此情况下,应选用哪种存储表示?为什么? (2)若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元 素,这时,应采用哪种存储表示?为什么? 23已知整数数组A[]中有n个元素,试设计一个算法,求数组中所有元素值的和。 24已知整数数组A[]中有n个元素,试设计一个算法,求数组中所有元素值的平均值。 25设有一个线性表(eoe,…cn-2,em)存放在一个一维数组 AlarraySize中的前n个数组元 素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个地址的内容置换为(em ,en-2,……,el,eo)e
数据结构与程序设计复习 2 float s = 0.0; for ( int i = 0; i < n; i++ ) s += a[i]; return s; } 1.6 试用大 O 表示法给出下面程序的时间复杂性。 void out ( float x[ ][ ], int m, int n ) { float sum[ ]; for ( int i = 0; i < m; i++ ) { sum[i] = 0.0; for ( int j = 0; j < n; j++ ) sum[i] = x[i][j]; } for ( int i = 0; i < m; i++ ) cout << "Line: " << i << ":" << sum[i] << endl; } 第二章 数组 2.1 判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 (1) 线性表的逻辑顺序与物理顺序总是一致的。 (2) 线性表的顺序存储表示优于链式存储表示。 (3) 线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。 (4) 二维数组是其数组元素为线性表的线性表。 (5) 每种数据结构都应具备三种基本运算：插入、删除和搜索。 2.2 线性结构可用顺序表或链表存储。试问： (1) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数 也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元 素，这时，应采用哪种存储表示？为什么？ 2.3 已知整数数组 A[ ]中有 n 个元素，试设计一个算法，求数组中所有元素值的和。 2.4 已知整数数组 A[ ]中有 n 个元素，试设计一个算法，求数组中所有元素值的平均值。 2.5 设有一个线性表 (e0, e1, …, en-2, en-1) 存放在一个一维数组 A[arraySize]中的前 n 个数组元 素位置。请编写一个函数将这个线性表原地逆置，即将数组的前 n 个地址的内容置换为 (en- 1, en-2, …, e1, e0)
数据结构与程序设计复习 26假定数组 A[ Size中有多个零元素,试写出一个函数将A中所有的非零元素依次移 到数组A的前端A[](0≤ilink=p->link; p->link=s, (2)q->link=S; s->link=p: (3)p-link=S->link; s->link=p:(4)p->link =S; s->link =q:
数据结构与程序设计复习 3 2.6 假定数组 A[arraySize]中有多个零元素, 试写出一个函数, 将 A 中所有的非零元素依次移 到数组 A 的前端 A[i] (0 i link = p->link; p->link = s; (2) q->link = s; s->link = p; (3) p->link = s->link; s->link = p; (4) p->link = s; s->link = q;
数据结构与程序设计复习 32设单链表中结点的结构为(data,link)。已知指针p所指结点不是尾结点,若在*p之 后插入结点*s,则应执行下列哪一个操作? (1)s->link=p: p->link =s, (2)s->link=p->link; p->link=s: ()s->link=p->link; p=s; (4)p->link =S; s->link =p; 33设单链表中结点的结构为(data,link)。若想摘除结点的直接后继,则应执行下列 哪一个操作? (1)p->link=p->link->link; (2)p=p->link; p->link=p->link->link ()p->link=p->link (4)p=p->link-> link 3.4已知head为单链表的表头指针,链表中存储的都是整型数据,试写出实现下列运算的 递归算法 (1)求链表中的最大整数 (2)求链表的结点个数 3.5设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所 有结点的链接方向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后 个结点 3.6设A和B是两个单链表,表中的元素均按结点的值(整数)升序排列。试编写一个函 数,将A和B归并成一个按结点的值降序排列的单链表C。要求辅助存储空间为O1) 3.7设单循环链表中结点的结构为( data link),且rear是指向非空的带表头结点的单循环 链表的尾结点的指针。若想删除链表第一个结点,则应执行下列哪一个操作? (1)s=rear; rear=rear-link; free(s) (2)rear= rear->link; free(rear) ()rear= rear->link->link; free(rear); (4)s=rear->link->link; rear->link->link =s->link, free(s) 38有一个循环链表,它既没有头指针又没有头结点。只有一个指针p指向表中的某一结 点。试编写一个函数,删除指针p所指结点的直接前驱结点。 39判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示,请在算法中的 处填入正确的语句。 int symmetry( DlinkList L)i
数据结构与程序设计复习 4 3.2 设单链表中结点的结构为（data, link）。已知指针 p 所指结点不是尾结点，若在*p 之 后插入结点*s，则应执行下列哪一个操作？ (1) s->link = p; p->link = s; (2) s->link = p->link; p->link = s; (3) s->link = p->link; p = s; (4) p->link = s; s->link = p; 3.3 设单链表中结点的结构为（data, link）。若想摘除结点*p 的直接后继，则应执行下列 哪一个操作？ (1) p->link = p->link->link; (2) p = p->link; p->link = p->link->link; (3) p->link = p->link; (4) p = p->link->link; 3.4 已知 head 为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的 递归算法： (1) 求链表中的最大整数。 (2) 求链表的结点个数。 3.5 设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所 有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针 h 指向原链表的最后 一个结点。 3.6 设 A 和 B 是两个单链表，表中的元素均按结点的值（整数）升序排列。试编写一个函 数，将 A 和 B 归并成一个按结点的值降序排列的单链表 C。要求辅助存储空间为 O(1)。 3.7 设单循环链表中结点的结构为（data, link），且 rear 是指向非空的带表头结点的单循环 链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？ (1) s = rear; rear = rear->link; free(s); (2) rear = rear->link; free(rear); (3) rear = rear->link->link; free(rear); (4) s = rear->link->link; rear->link->link = s->link; free(s); 3.8 有一个循环链表，它既没有头指针又没有头结点。只有一个指针 p 指向表中的某一结 点。试编写一个函数，删除指针 p 所指结点的直接前驱结点。 3.9 判断一个带表头结点的双向循环链表 L 是否对称相等的算法如下所示，请在算法中的 处填入正确的语句。 int symmetry ( DlinkList L ) { pr h h Λ Λ Λ
数据结构与程序设计复习 int sym=l; DlistNode*p=L->next, q=L->prior; while(pl=q‖p-> prior==q)&&_①) if( p->data ==q->data)i else sym=0 return svm 3.10设双向循环链表中结点的结构为(data, prior,next),且不带表头结点。若想在指针p 所指结点之后插入指针s所指结点,则应执行下列哪一个操作? (1)p->next=s, s->prior=p; p->next->prior =s; s->next=p->next; (2)p->next=S; p->next->prior =S; s->prior =p, s->next=p->next (3)s->prior=p; s->next=p->next; p->next=S, p->next->prior =s, (4)s->prior=p,s >prior= s, p->next =S, 311试设计一个实现下述要求的查找运算函数 Locate(Llx)。设有一个带表头结点的双向链 表L,每个结点有4个数据成员:指向前驱结点的指针 prior、指向后继结点的指针next 存放数据的成员data和访问频度freq。所有结点的feq初始时都为0。每当在链表上进行 次 Locate(Lx)操作时,令元素值为x的结点的访问频度feq加1,并将该结点前移,链 接到与它的访问频度相等的结点后面,使得链表中所有结点保持按访问频度递减的顺序排 列,以使频繁访问的结点总是靠近表头。 第四章栈和队列 4.1试回答下列问题: (1)设整数1,2,3,4,5,6依次进栈,则可能的出栈序列有多少种? (2)若整数1,2,3,4,5,6依次进栈,那么是否能够得到435612,325641,154623和 135426的出栈序列。 42设有一个顺序栈S,元素s,s2,s3,S,S,S6依次进栈,如果6个元素的出栈顺序为s2,s, S4,s,s,s,则顺序栈的容量至少应为多少? 43设顺序栈S的元素个数最大为 Max size。试改写顺序栈的进栈函数Push(S,x),要求当 栈满时执行一个 sackfUl(S)操作进行栈满处理。其功能是:动态创建一个比原来的栈元素 存放数组大二倍的新数组,代替原来的栈元素存放数组,原来栈元素存放数组中的元素占 据新数组的前 Max size位置。 44设链式栈中结点的结构为(data,link),且tqp是指向栈顶的指针。若想在链式栈的栈 顶插入一个由指针s所指的结点,则应执行下列哪一个操作?
数据结构与程序设计复习 5 int sym = 1; DlistNode * p = L->next, q = L->prior; while ( ( p != q || p->prior == q ) && ① ) if ( p->data == q->data ) { ② ; ③ ; } else sym = 0; return sym; } 3.10 设双向循环链表中结点的结构为（data, prior, next），且不带表头结点。若想在指针 p 所指结点之后插入指针 s 所指结点，则应执行下列哪一个操作？ (1) p->next = s; s->prior = p; p->next->prior = s; s->next = p->next; (2) p->next = s; p->next->prior = s; s->prior = p; s->next = p->next; (3) s->prior = p; s->next = p->next; p->next = s; p->next->prior = s; (4) s->prior = p; s->next = p->next; p->next->prior = s; p->next = s; 3.11 试设计一个实现下述要求的查找运算函数 Locate(L, x)。设有一个带表头结点的双向链 表 L，每个结点有 4 个数据成员：指向前驱结点的指针 prior、指向后继结点的指针 next、 存放数据的成员 data 和访问频度 freq。所有结点的 freq 初始时都为 0。每当在链表上进行 一次 Locate (L, x)操作时，令元素值为 x 的结点的访问频度 freq 加 1，并将该结点前移，链 接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排 列，以使频繁访问的结点总是靠近表头。 第四章 栈和队列 4.1 试回答下列问题： (1) 设整数 1, 2, 3, 4, 5, 6 依次进栈，则可能的出栈序列有多少种? (2) 若整数 1, 2, 3, 4, 5, 6 依次进栈，那么是否能够得到 435612, 325641, 154623 和 135426 的出栈序列。 4.2 设有一个顺序栈 S，元素 s1, s2, s3, s4, s5, s6 依次进栈，如果 6 个元素的出栈顺序为 s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？ 4.3 设顺序栈 S 的元素个数最大为 MaxSize。试改写顺序栈的进栈函数 Push (S, x)，要求当 栈满时执行一个 stackFull(S) 操作进行栈满处理。其功能是：动态创建一个比原来的栈元素 存放数组大二倍的新数组，代替原来的栈元素存放数组，原来栈元素存放数组中的元素占 据新数组的前 MaxSize 位置。 4.4 设链式栈中结点的结构为（data, link），且 top 是指向栈顶的指针。若想在链式栈的栈 顶插入一个由指针 s 所指的结点，则应执行下列哪一个操作？
数据结构与程序设计复习 (1)top->link=s (2)s->link=top->link; top->link=s (3)s->link (4)s->link=top; top= top->link 4.5设链式栈中结点的结构为(data,link),且tqp是指向栈顶的指针。若想摘除链式栈的 栈顶结点,并将被摘除结点的值保存到x中,则应执行下列哪一个操作? (1)x=top->data; top= top->link; (2)top=top->link; x=top->data ()x=top, top=top->link 46假设以数组Qm存放循环队列中的元素,同时以rear和 length分别指示循环队列中的 队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应 的插入( EnQueue)和删除( DIQueue)元素的操作。 47假设以数组Qm]存放循环队列中的元素,同时设置一个标志tag,以tag=0和tag=1 来区别在队头指针( front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写 与此结构相应的插入( EnQueue)和删除( DIQueue的函数 48若使用循环链表来表示队列,p是链表中的一个指针(视为队尾指针)。试基于此结构给 出队列的插入( EnQueue)和删除 (DIQueue函数,并给出p为何值时队列空 第六章树与森林 6.1一棵具有n个结点的理想平衡二叉树(即除离根最远的最底层外其他各层都是满的, 最底层有若干结点)有多少层?若设根结点在第0层,则树的高度如何用n来表示(注意 n可能为0)? 62n个结点可构造出多少种不同形态的二叉树?若有3个数据1,2,3,输入它们构造出来 的中序遍历结果都为1,2,3的不同二叉树有哪些? 63假定在一棵二叉树中,度为2的结点有15个,度为1的结点有20个,试问度为0的 结点有多少个? 64判断下列叙述的对错。如果正确,在题前打“√”,否则打“x” (1)二叉树是树的特殊情形 (2)若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点,则它一定 是该子树的前序遍历结果序列的最后一个结点。 (3)若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定 是该子树的中序遍历结果序列的最后一个结点 (4)若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点,则它 定是该子树的前序遍历结果序列的最后一个结点。 (5)若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它 定是该子树的中序遍历结果序列的最后一个结点
数据结构与程序设计复习 6 (1) top->link = s; (2) s->link = top->link; top->link = s; (3) s->link = top; top = s; (4) s->link = top; top = top->link; 4.5 设链式栈中结点的结构为（data, link），且 top 是指向栈顶的指针。若想摘除链式栈的 栈顶结点，并将被摘除结点的值保存到 x 中，则应执行下列哪一个操作？ (1) x = top->data; top = top->link; (2) top = top->link; x = top->data; (3) x = top; top = top->link; (4) x = top->data; 4.6 假设以数组 Q[m]存放循环队列中的元素, 同时以 rear 和 length 分别指示循环队列中的 队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应 的插入(EnQueue)和删除(DlQueue)元素的操作。 4.7 假设以数组 Q[m]存放循环队列中的元素, 同时设置一个标志 tag，以 tag = 0 和 tag = 1 来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写 与此结构相应的插入(EnQueue)和删除(DlQueue)的函数。 4.8 若使用循环链表来表示队列，p 是链表中的一个指针(视为队尾指针)。试基于此结构给 出队列的插入(EnQueue)和删除(DlQueue)的函数，并给出 p 为何值时队列空。 第六章 树与森林 6.1 一棵具有 n 个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的， 最底层有若干结点）有多少层？若设根结点在第 0 层，则树的高度如何用 n 来表示（注意 n 可能为 0）？ 6.2 n 个结点可构造出多少种不同形态的二叉树? 若有 3 个数据 1, 2, 3，输入它们构造出来 的中序遍历结果都为 1, 2, 3 的不同二叉树有哪些? 6.3 假定在一棵二叉树中，度为 2 的结点有 15 个，度为 1 的结点有 20 个，试问度为 0 的 结点有多少个？ 6.4 判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 (1) 二叉树是树的特殊情形。 (2) 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定 是该子树的前序遍历结果序列的最后一个结点。 (3) 若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定 是该子树的中序遍历结果序列的最后一个结点。 (4) 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它 一定是该子树的前序遍历结果序列的最后一个结点。 (5) 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它 一定是该子树的中序遍历结果序列的最后一个结点
数据结构与程序设计复习 65试分别画出满足以下条件的所有二叉树: (1)二叉树的前序序列与中序序列相同 (2)二叉树的中序序列与后序序列相同 (3)二叉树的前序序列与后序序列相同。 66已知一棵二叉树的前序遍历结果是 ABECDFGHI,中序遍历结果是 EBCDAFHIGJ,试画 出这棵二叉树 67若用二叉链表作为二叉树的存储表示,试编写一个递归算法求二叉树中指定结点所在 层次。(设二叉树的高度为h,空树时h=-1,只有一个结点的二叉树的高度为h=0) 68已知一棵完全二叉树存放于一个一维数组Tn]中,Tn]中存放的是各结点的值。试设计 个算法,从T开始顺序读出各结点的值,建立该二叉树的二叉链表表示。 69下面是一个二叉树的前序遍历的递归算法。 void PreOrder( BinTreeNode *t)i if(t I=NULL )4 ∥递弟归结束条件 cout data: ∥访问(输出)根结点 PreOrder( t->leftChild ∥前序遍历左子树 PreOrder( t->rightChild ) ∥前序遍历右子树 (1)改写 PreOrder算法,消去第二个递归调用 PreOrder(t-> rightchild); (3)利用栈改写 PreOrder算法,消去两个递归调用。 610设二叉树采用二叉链表表示,指针roo指向根结点,指针p指向二叉树中某一指定结 点。试编写一个算法,找出从根结点到结点*p之间的路径 6.11从供选择的答案中选择与下面有关二叉树和森林的叙述中各括号相匹配的词句,将其 编号填入相应的括号内。 (1)设二叉树有n个结点且根结点处于第0层,则其高度为(A) (2)设高度为h(空二叉树的高度为-1,只有一个结点的二叉树的高度为0)的二叉树 只有度为2和度为0的结点,则该二叉树中所含结点至少有(B)个 (3)设森林F中有4棵树,第1、2、3、4棵树的结点个数分别为m、n、n 当把 森林F转换成一棵二叉树后,其根结点的右子树中有(C)个结点 (4)设森林F中有4棵树,第1、2、3、4棵树的结点个数分别为m、n、n 当把 森林F转换成一棵二叉树后,其根结点的左子树中有(D)个结点。 (5)将含有82个结点的完全二叉树从根结点开始顺序编号,根结点为第0号,其他结 点自上向下,同一层自左向右连续编号。则第40号结点的双亲结点的编号为(E)。 【供选择的答案】 A:①n-1 ②「log2(n+1)1 ③og2n+1 ④不确定 B:①2h ②22h-1 ③2h+1 ④h+1
数据结构与程序设计复习 7 6.5 试分别画出满足以下条件的所有二叉树： (1) 二叉树的前序序列与中序序列相同； (2) 二叉树的中序序列与后序序列相同； (3) 二叉树的前序序列与后序序列相同。 6.6 已知一棵二叉树的前序遍历结果是 ABECDFGHIJ, 中序遍历结果是 EBCDAFHIGJ, 试画 出这棵二叉树。 6.7 若用二叉链表作为二叉树的存储表示，试编写一个递归算法求二叉树中指定结点所在 层次。(设二叉树的高度为 h，空树时 h = -1，只有一个结点的二叉树的高度为 h = 0) 6.8 已知一棵完全二叉树存放于一个一维数组 T[n]中，T[n]中存放的是各结点的值。试设计 一个算法，从 T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 6.9 下面是一个二叉树的前序遍历的递归算法。 void PreOrder ( BinTreeNode *t ) { if ( t != NULL ) { //递归结束条件 cout data; //访问(输出)根结点 PreOrder ( t->leftChild ); //前序遍历左子树 PreOrder ( t->rightChild ); //前序遍历右子树 } } (1) 改写 PreOrder 算法，消去第二个递归调用 PreOrder (t->rightChild ); (3) 利用栈改写 PreOrder 算法，消去两个递归调用。 6.10 设二叉树采用二叉链表表示，指针 root 指向根结点，指针 p 指向二叉树中某一指定结 点。试编写一个算法，找出从根结点到结点*p 之间的路径。 6.11 从供选择的答案中选择与下面有关二叉树和森林的叙述中各括号相匹配的词句，将其 编号填入相应的括号内。 (1) 设二叉树有 n 个结点且根结点处于第 0 层，则其高度为（ A ）。 (2) 设高度为 h（空二叉树的高度为-1，只有一个结点的二叉树的高度为 0）的二叉树 只有度为 2 和度为 0 的结点，则该二叉树中所含结点至少有（ B ）个。 (3) 设森林 F 中有 4 棵树，第 1、2、3、4 棵树的结点个数分别为 n1、n2、n3、n4，当把 森林 F 转换成一棵二叉树后，其根结点的右子树中有（ C ）个结点。 (4) 设森林 F 中有 4 棵树，第 1、2、3、4 棵树的结点个数分别为 n1、n2、n3、n4，当把 森林 F 转换成一棵二叉树后，其根结点的左子树中有（ D ）个结点。 (5) 将含有 82 个结点的完全二叉树从根结点开始顺序编号，根结点为第 0 号，其他结 点自上向下，同一层自左向右连续编号。则第 40 号结点的双亲结点的编号为（ E ）。 【供选择的答案】 A：① n-1 ② log2(n+1) -1 ③ log2n +1 ④ 不确定 B：① 2h ② 2h -1 ③ 2h +1 ④ h +1 C~D：① n1-1 ② n1+n2+n3 ③ n2+n3+n4 ④ n1
数据结构与程序设计复习 E:①20 ③81 612一棵高度为h的满k叉树有如下性质:第h层上的结点都是叶结点,其余各层上每个结 点都有k棵非空子树,如果按层次自顶向下,同一层自左向右,顺序从1开始对全部结点进行 编号,试问 (1)各层的结点个数是多少? (2)编号为i的结点的父结点(若存在)的编号是多少? (3)编号为i的结点的第m个孩子结点(若存在)的编号是多少? (4)编号为i的结点有右兄弟的条件是什么?其右兄弟结点的编号是多 5)若结点个数为n,则高度h是n的什么函数关系? 613判断以下序列是否是最小堆?如果不是,将它调整为最小堆。 (1){100,86,48,73,35,39,42,57,66,21} (2){12,70,33,65,24,56,48,92,86,33 614给定权值集合{15,03,14,02,06,09,16,17},构造相应的 Huffman树,并计算它的带权 外部路径长度 615假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成各字母在电文中出 现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长 Huffman编码,并给出 该电文的总码数。 第七章集合与搜索 7.1供选择的答案中选择与下面有关搜索算法的叙述中各括号相匹配的词句,将其编号填 入相应的括号内 (1)对线性表进行折半搜索时,要求线性表必须(A (2)采用顺序搜索算法查找长度为n的线性表时,元素的平均搜索长度为(B (3)采用折半搜索算法查找长度为n的线性表时,元素的平均搜索长度为(C)。 (4)折半搜索与二叉搜索树(即二叉排序树)的时间性能(D) 5)顺序搜索算法适合于存储结构为(E)的线性表 【供选择的答案】 A:①以数组方式存储②以数组方式存储且结点按关键码有序排列 ③以链接方式存储 ④以链接方式存储且结点按关键码有序排列 B:①n/2 ② ③(n+1)2 ④(n-1)2 oCn- en) D:①相同 ②不相同 E:①散列存储 ②顺序存储或链接存储 ③压缩存储 ④索引存储 7.2设有序顺序表中的元素依次为017,094,154,170,275,503,509,512553,612,677765 897,908。试画出对其进行顺序搜索时的判定树,并计算搜索成功的平均搜索长度和搜索不 成功的平均搜索长度
数据结构与程序设计复习 8 E：① 20 ② 19 ③ 81 ④ 80 6.12 一棵高度为 h 的满 k 叉树有如下性质: 第 h 层上的结点都是叶结点, 其余各层上每个结 点都有 k 棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从 1 开始对全部结点进行 编号, 试问: (1) 各层的结点个数是多少? (2) 编号为 i 的结点的父结点(若存在)的编号是多少? (3) 编号为 i 的结点的第 m 个孩子结点(若存在)的编号是多少? (4) 编号为 i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度 h 是 n 的什么函数关系? 6.13 判断以下序列是否是最小堆? 如果不是, 将它调整为最小堆。 (1) { 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 } (2) { 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } 6.14 给定权值集合{ 15, 03, 14, 02, 06, 09, 16, 17 }, 构造相应的 Huffman 树, 并计算它的带权 外部路径长度。 6.15 假定用于通信的电文仅由 8 个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成, 各字母在电文中出 现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4。试为这 8 个字母设计不等长 Huffman 编码, 并给出 该电文的总码数。 第七章 集合与搜索 7.1 供选择的答案中选择与下面有关搜索算法的叙述中各括号相匹配的词句，将其编号填 入相应的括号内。 (1) 对线性表进行折半搜索时，要求线性表必须（ A ）。 (2) 采用顺序搜索算法查找长度为 n 的线性表时，元素的平均搜索长度为（ B ）。 (3) 采用折半搜索算法查找长度为 n 的线性表时，元素的平均搜索长度为（ C ）。 (4) 折半搜索与二叉搜索树（即二叉排序树）的时间性能（ D ）。 (5) 顺序搜索算法适合于存储结构为（ E ）的线性表。 【供选择的答案】 A：① 以数组方式存储 ② 以数组方式存储且结点按关键码有序排列 ③ 以链接方式存储 ④ 以链接方式存储且结点按关键码有序排列 B：① n/2 ② n ③ (n+1)/2 ④ (n-1)/2 C：① O(n2 ) ② O(nlog2n) ③ O(log2n) ④ O(n) D：① 相同 ② 不相同 E：① 散列存储 ② 顺序存储或链接存储 ③ 压缩存储 ④ 索引存储 7.2 设有序顺序表中的元素依次为 017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行顺序搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不 成功的平均搜索长度
数据结构与程序设计复习 7.3设有序顺序表中的元素依次为017,094,154,170,275,503,509,512553,612,677765 897,908。试画出对其进行折半搜索时的判定树,并计算搜索成功的平均搜索长度和搜索不 成功的平均搜索长度。 74设有一个关键码序列{DEC,FEB,NOV,OCT,JUL,SEP,AUG, APR, MAR MAY,JUN JANI 1)按字母顺序依次插入到一棵初始为空的AVL树中,画出每插入一个关键码后的 AVL树,并标明平衡旋转的类型。 (2)从所建立的AVL树中删除关键码MAY,为保持AVL树的特性,应如何进行删除 和调整?若接着删除关键码FEB,又应如何删除与调整? 75设有一个关键码的输入序列{55,31,11,37,46,73,63,02,07} (1)从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。若发生 不平衡,指明需做的平衡旋转的类型及平衡旋转的结果。 (2)计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均 查找长度 7.6对于一个高度为h的AVL树,其最少结点数是多少?反之,对于一个有n个结点的 AVL树,其最大高度是多少?最小高度是多少? 第八章图 81判断下列叙述的对错。如果正确,在题前打“√”,否则打“x (1)用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只 与图中的顶点个数有关,而与图的边数无关 (2)对任何用顶点表示活动的网络(AOV网)进行拓扑排序的结果都是唯一的 (3)有回路的有向图不能完成拓扑排序。 (4)有n(n≥1)个顶点的无向连通图最少有n-1条边。 (5)有n(n≥1)个顶点的有向强连通图最少有n条边 82从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句,将其编号填入相 应的括号内 (1)对于一个具有n个结点和e条边的无向图,若采用邻接表表示,则顶点表的大小为 (A),所有边链表中边结点的总数为(B) (2)采用邻接表存储的图的深度优先遍历算法类似于二叉树的(C)。 (3)采用邻接表存储的图的广度优先遍历算法类似于二叉树的(D)。 (4)判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用(E)。 【供选择的答案】 A:①n ④n+e B:①e/2 ② ③2 ④n+e C~D:①中序遍历②前序遍历③后序遍历④按层次遍历
数据结构与程序设计复习 9 7.3 设有序顺序表中的元素依次为 017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不 成功的平均搜索长度。 7.4 设有一个关键码序列 {DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN} (1) 按字母顺序依次插入到一棵初始为空的 AVL 树中，画出每插入一个关键码后的 AVL 树，并标明平衡旋转的类型。 (2) 从所建立的 AVL 树中删除关键码 MAY，为保持 AVL 树的特性，应如何进行删除 和调整? 若接着删除关键码 FEB，又应如何删除与调整? 7.5 设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }, (1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生 不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。 (2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均 查找长度。 7.6 对于一个高度为 h 的 AVL 树，其最少结点数是多少？反之，对于一个有 n 个结点的 AVL 树, 其最大高度是多少? 最小高度是多少? 第八章 图 8.1 判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 (1) 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只 与图中的顶点个数有关，而与图的边数无关。 (2) 对任何用顶点表示活动的网络(AOV 网)进行拓扑排序的结果都是唯一的。 (3) 有回路的有向图不能完成拓扑排序。 (4) 有 n (n≥1) 个顶点的无向连通图最少有 n-1 条边。 (5) 有 n (n≥1) 个顶点的有向强连通图最少有 n 条边。 8.2 从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相 应的括号内。 (1) 对于一个具有 n 个结点和 e 条边的无向图，若采用邻接表表示，则顶点表的大小为 （ A ），所有边链表中边结点的总数为（ B ）。 (2) 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ C ）。 (3) 采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ D ）。 (4) 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ E ）。 【供选择的答案】 A：① n ② n+1 ③ n-1 ④ n+e B：① e/2 ② e ③ 2e ④ n+e C~D：① 中序遍历 ② 前序遍历 ③ 后序遍历 ④ 按层次遍历
数据结构与程序设计复习 E:①求关键路径的方法 ②求最短路径的 Dijkstra方法 ③深度优先遍历算法 ④广度优先遍历算法 83试利用 Dijkstra逐步求解的算法,计算下面带权有向图中从顶点A到其他各顶点的最 短路径。 84是否可将表示AOV网的邻接矩阵中所有的非零元素全部集中到矩阵的上三角部分(即 矩阵的对角线以上的部分),试举例说明 85画出下图所示的AOV网的所有拓扑有序序列。 6若用一个连通图来表示一个通信网络,如图所示。 4 其中,顶点表示网络中的通信站点,边表示网络中的通信线路,则 (1)画出从顶点①出发的深度优先生成树; (2)在原来的图中补充几条边,使其中某一站点失效时整个通信网络仍然保持畅通。 (3)指出图中哪几个顶点是关节点(即万一它失效则通信网络将发生故障)。 第九章排序 9.1如果只想在一个有n个元素的任意序列中得到其中最小的第k(k远小于n)个元素之前 的部分排序序列,那么最好采用什么排序方法?为什么?例如有这样一个序列:{503,017,512, 908,170,897,275,653,612,154,509,612*,677,765,094},要得到其第4个元素之前的部分 有序序列:{017,094,154,170},用所选择的算法实现时,要执行多少次比较? 9.2直接选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明
数据结构与程序设计复习 10 E：① 求关键路径的方法 ② 求最短路径的 Dijkstra 方法 ③ 深度优先遍历算法 ④ 广度优先遍历算法 8.3 试利用 Dijkstra 逐步求解的算法，计算下面带权有向图中从顶点 A 到其他各顶点的最 短路径。 8.4 是否可将表示 AOV 网的邻接矩阵中所有的非零元素全部集中到矩阵的上三角部分（即 矩阵的对角线以上的部分），试举例说明。 8.5 画出下图所示的 AOV 网的所有拓扑有序序列。 8.6 若用一个连通图来表示一个通信网络, 如图所示。 其中, 顶点表示网络中的通信站点, 边表示网络中的通信线路, 则 (1) 画出从顶点①出发的深度优先生成树; (2) 在原来的图中补充几条边, 使其中某一站点失效时整个通信网络仍然保持畅通。 (3) 指出图中哪几个顶点是关节点(即万一它失效则通信网络将发生故障)。 第九章 排序 9.1 如果只想在一个有 n 个元素的任意序列中得到其中最小的第 k (k 远小于 n) 个元素之前 的部分排序序列, 那么最好采用什么排序方法? 为什么? 例如有这样一个序列: { 503, 017, 512, 908, 170, 897, 275, 653, 612, 154, 509, 612*, 677, 765, 094 }, 要得到其第 4 个元素之前的部分 有序序列: { 017, 094, 154, 170 }, 用所选择的算法实现时, 要执行多少次比较? 9.2 直接选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。 A B C D E 10 18 5 5 2 2 2 A B C D E F