数据结构与程序设计复习 第一章数据结构概论 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≤i< arraySize) 27已知A[n为整数数组,试写出实现下列运算的递归算法 (1)求数组A中的最大整数 (2)求n个整数的和 28设有一个二维数组A[m][n,假设AOI0]存放位置在64410,A[2]2存放位置在 67610,每个元素占一个空间,问A[4]4在什么位置,下标(10表示用10进数表示 29设有上三角矩阵A[nn],将其上三角元素逐行存储到一维数组Bm]中,使得Bk] A[,且k=f1(+f2()+C。试推导出函数f(i)、f()和常数C,要求f1(1)和f2(中不 包含常数项 2.10设A和B均为下三角矩阵,每一个都有n行。因此在下三角区域中各有nn+1)2个元 素。另设有一个二维数组C,它有n行n+1列。试设计一个方案,将两个矩阵A和B中的 下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区 域中,B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元 素a和B的矩阵元素b在C中的存放位置下标的公式 211设有三对角矩阵A[n[n,将其三条对角线中的元素逐行存储到一维数组B[3n2]中, 使得Bk]=A[][]。试求: (1)用i,j表示k的地址转换公式; (2)用k表示,j的地址转换公式; 2.12顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127 个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少 个元素? 2.13已知一个顺序表中的元素按元素值非递减有序排列,试定义顺序表的存储表示,并编 写一个函数,删除表中值相同的多余元素 2.14设有两个整数类型的顺序表A(有m个元素)和B(有n个元素),其元素均以从小 到大的升序排列。试编写一个函数,将这两个顺序表合并成一个顺序表C,要求C的元素 也以从小到大的升序排列 第三章链表 3.1设单链表中结点的结构为(data,ink)。已知指针q所指结点是指针p所指结点的直接 前驱,若在*q与*之间插入结点*s,则应执行下列哪一个操作? (1)s->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:
数据结构与程序设计复习 3 2.6 假定数组 A[arraySize]中有多个零元素, 试写出一个函数, 将 A 中所有的非零元素依次移 到数组 A 的前端 A[i] (0 i < arraySize)。 2.7 已知 A[n]为整数数组，试写出实现下列运算的递归算法： (1) 求数组 A 中的最大整数。 (2) 求 n 个整数的和。 2.8 设有一个二维数组 A[m][n]，假设 A[0][0]存放位置在 644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问 A[4][4]在什么位置，下标(10)表示用 10 进数表示。 2.9 设有上三角矩阵 A[n][n]，将其上三角元素逐行存储到一维数组 B[m]中，使得 B[k] = A[i][j]，且 k = f1 (i) + f2 (j) + C。试推导出函数 f1 (i)、f2 (j)和常数 C，要求 f1 (i)和 f2 (j)中不 包含常数项。 2.10 设 A和 B 均为下三角矩阵，每一个都有 n 行。因此在下三角区域中各有 n(n+1)/2 个元 素。另设有一个二维数组 C，它有 n 行 n+1 列。试设计一个方案，将两个矩阵 A 和 B 中的 下三角区域元素存放于同一个 C 中。要求将 A 的下三角区域中的元素存放于 C 的下三角区 域中，B 的下三角区域中的元素转置后存放于 C 的上三角区域中。并给出计算 A 的矩阵元 素 aij 和 B 的矩阵元素 bij 在 C 中的存放位置下标的公式。 2.11 设有三对角矩阵 A[n][n]，将其三条对角线中的元素逐行存储到一维数组 B[3n-2 ]中， 使得 B[k] = A[i][j]。试求： (1) 用 i, j 表示 k 的地址转换公式； (2) 用 k 表示 i, j 的地址转换公式； 2.12 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有 127 个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少 个元素? 2.13 已知一个顺序表中的元素按元素值非递减有序排列，试定义顺序表的存储表示，并编 写一个函数，删除表中值相同的多余元素。 2.14 设有两个整数类型的顺序表 A（有 m 个元素）和 B（有 n 个元素），其元素均以从小 到大的升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表 C，要求 C 的元素 也以从小到大的升序排列。 第三章 链表 3.1 设单链表中结点的结构为（data, link）。已知指针 q 所指结点是指针 p 所指结点的直接 前驱，若在*q 与*p 之间插入结点*s，则应执行下列哪一个操作？ (1) s->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 所指的结点，则应执行下列哪一个操作？