济南铁道职业技术学院 专升本辅导教材 数据结构
(3)采用程序设计语言编写的程序也是算法。 ( ) (4)一个算法可以没有输入，但不能没有输出。 ( )
(5)顺序存储结构通过数据元素的地址直接反映数据元素间的逻辑关系。 ( ) (6)链式存储结构通过指针间接地反映数据元素之间的逻辑关系。 ( ) (7)数据的存储结构通常只有顺序存储结构与链式存储结构两种。 ( ) (8)具有相同逻辑结构的数据可以采用不同的存储结构。 ( ) (9)逻辑结构不相同的数据应该采用不同的存储结构。 ( ) (10)算法分析的前提是算法的时空效率高， ( ) 1．2 填空题。
(1)“数据结构”课程研究的主要内容包括——、——和——三个方面。 (2)一般情况下，算法独立于具体的——，与具体的程序设计语言——。 (3)一个完整的算法应该具有——、——、——、——和——五个特性。 (4)数据的逻辑结构可以分为——和——两大类。
(5)除了顺序存储结构与链式存储结构之外，数据的存储结构通常还有——和散列结构。 (6)数据的逻辑结构是指——，而存储结构是指——。
(7)逻辑上相邻的数据元素在物理位置上也相邻是——存储结构的特点之一。 (8)为了实现随机访问，线性结构应该采用——存储结构。 (9)链式存储结构的主要优点是——。
(10)算法分析主要从——和——这两个方面对算法进行分析。
1．3 通常说数据结构是一个二元组(D，R)，其中D，R分别代表什么? 1．4 何谓数据的逻辑结构?何谓数据的存储结构?两者有何联系?
历年试题 一
1．在数据结构中，数据的逻辑结构可以分成（ ）
A．内部结构和外部结构 B．线性结构和非线性结构 C．紧凑结构和非紧揍结构 D．动态结构和静态结构 2．下列说法正确的是（ ）
A．数据是数据元素的基本单位
B．数据元素是数据项中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成 3．数据结构的基本任务是（ ）
A．逻辑结构和存储结构的设计 B．数据结构的运算实现 C．数据结构的评价与选择 D．数据结构的设计与实现
4．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）
2
A．O（1） B．O（n） C．O（nlog2n） D．O(n)
5.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 6、选出正确的表述
(1)顺序存储方式只能用于存储线性结构。
第 5 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
(2)顺序存储方式的优点是存储密度大, 且插入、删除运用算效率高。 (3)链表的每个结点中都恰好包含一个指针。
(4)散列法存储的基本思想是由关键码的值决定数据的存储地址。 (5)散列表的结点中只包含数据元素自身的信息, 不包含任何指针。
(6)负载因子 (装填因子) 是散列法的一个重要参数, 它反映散列表的装满程度。 (7)栈和队列的存储方式既可是顺序方式, 也可是链接方式。
(8)用二叉链表法 (llink -- rlink法) 存储包含n 个结点的二叉树, 结点的2n个指针区域中有n+1 个为空指针。
(9)用相邻矩阵法存储一个图时, 在不考虑压缩存储的情况下, ?所占用的存储空间大小只与图中结点个数有关, 而与图的边数无关。
(10)邻接表法只能用于有向图的存储,而相邻矩阵法对于有向图和无向图的存储都适用。
7．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。
8．下列程序段的时间复杂度为________________。 product = 1; for (i = n;i>0; i--)
for (j = i+1; j 9．文件上的两类主要操作为________________和________________。 10．文件的基本运算包括______________和修改两类。 11．下列程序段的时间复杂性量级是_____________。 for (i=1;i t=t+1; 12.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为________。 第二章 课后辅导 例2．1 已知长度为n的非空线性表A采用顺序存储结构，表中数据元素按值的大小非递减排列，请写出删除该线性表中值相同的多余元素的算法。7654321 7654321 算法思想比较简单，只需从表的第一个数据元素开始到最后那个数据元素，反复做以下动作：比较相邻的两个数据元素是否相同，若相同，则删除其中一个；若不相同，则比较下一对相邻元素。算法如下： voidDELETEITEM1(ElemTypeA[]，int n)) { int j，i=0； while(i if (A[i]!=A[i+1]) ／x若相邻两个元素不相同。／ i++； else{ ／*若相邻两个元素相同，则删除其中一个*／ for ( j=i++；i n--； ／x表长减1 x／ 第 6 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 } } } 2 上述算法的时间复杂度为O(n)。对算法进行改进，得到一个时间复杂度为O(n)的 算法不是很困难。这里，设置两个整型变量i与k，它们的初值分别为1与0。若在比较 过程中发现A[i]与A[k]不同，则先将k后移一个位置，然后将A[i]送到A[k]的位置上； 若A[i]与A[k]相同，只是将i后移一个位置。当表中所有元素都处理完毕时，k+1正好 是删除多余元素以后线性表的长度。 改进后的算法如下： voidDELETEITEM2(ElemTypeA[]，int &n) { int k，i； if(n>1) { k=0； for(i=1；i if(A[i]!=A[k]) ／x若A[i]与A[k]不相同时。／ A[++k]=A[i]； n=k+1； ／。得到删除以后的表长。／ } } 14．将两个按值有序的非空线性链表合并为一个按值有序的线性链表 设lista与listb分别为两个有序链表第一个链结点的指针。将这两个有序链表合并 为一个有序链表，其第一个链结点的指针为listc。 这里，只需设置三个指针p，q和r，其中，p和q分别指向链表lista和链表listb当前待比较插入的链结点，而r指向链表listc中当前最后那个链结点。然后不断地比较p与q 所指的链结点的数据域值，若p->data < q->data，则将p指的链结点链接到r所指的链结点之后，否则将q指的链结点链接到r所指的链结点之后。当其中一个链表为空时，只 需将另一个链表中剩余的链结点都依次链接到r所指的链结点之后即可。初始时，让 listc指向lista和listb所指向的链结点中值小的那一个链结点。 LinkListMERGELIST(LinkListlista,LinkListlistb) { LinkList listc，p，q，r； if(lista->dada<=listb->data){ listc=lista； r=lista； p=lista->link； } else{ listc=listb； r=listb； q=listb->link； } ／x listc指向lista和listb所指结点中值小者x／ while(p!=NULL&&q!=NULL){ if(p->data<=q->data){／x若当前p所指结点的值不大于q所指结点的值x／ 第 7 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 r->link=p； ／y将p所指结点链接到r所指结点之后x／ r=p； p=p->link； } else{ r->link=q； ／。将q所指结点链接到r所指结点之后‘／ r=q； q=q—>link； } } r->link=p?p=q； ／x插人剩余链结点x／ return(listc)； ／x返回合并后的链表第一个链结点地址x／ } 若两个链表的长度分别为n与m，则上述算法的时间复杂度为O(n十m)。在合并两 个链表为一个链表时不需要另外建立新链表的链结点空间，只需将给定的两个链表中的 链结点之间的链接关系解除，重新按照元素值的非递减关系将所有链结点链接成为一个 链表即可。 例2．5 约瑟夫(Josephu)问题 已知n个人(不妨以编号1，2，3，?，n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列，他的下一个人又从1开始报数，数到m的那个人又出列，依此规则重复下去，直到圆桌周围的人全部出歹，J。 例如，当n：8，m’4，k二3时，出列的顺序依次为6，2，7，4，3，5，1，8。 解决约瑟夫问题可以利用多种数据结构，但比较简单和自然的方法是利用一个具有 n个链结点、且不带头结点的循环链表。将圆桌周围的每一个人对应着该链表中的一个链结点，某个人出列相当于从链表中删除一个链结点。下面的算法就是在该循环链表中不断地报数，不断地删除一个链结点，直到循环链表中还剩一个链结点时游戏结束。整个算法可以分为三个部分： (1)建立一个具有n个链结点且无头结点的循环链表； (2)确定第一个报数点的位置； (3)不断地从链表中删除一个链结点，直至链表中还有一个链结点。 习 题 2．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)空线性表的特征是表中数据元素都未赋值。 ( ) (2)线性表的顺序存储结构必须占用一片地址连续的存储单元。 ( ) (3)用一维数组存储线性表时，表中第i个元素存放在下标为i的数组元素中。 ( ) (4)采用顺序存储结构的线性表又称为顺序表。 ( ) (5)—个数据元素的地址是指该元素占用的若干存储单元的第一个单元的地址。 ( ) (6)线性表占用的存储单元的数量与表中数据元素的类型有关。 ( ) (7)线性表的顺序存储结构要比链式存储结构节省存储空间。 ( ) (8)线性表的链式存储结构要比顺序存储结构节省存储空间。 ( ) (9)若线性表采用顺序存储结构,线性表的长度等于表中元素的个数与每个元素所占内存单元之乘积。 ( ) 第 8 页 共 63 页
相关推荐：
loading