数据结构填空题
1.数据元素是（数据）的基本单位，是对一个客观实体的数据描述。
2.简单的说，数据结构是指数据之间的（逻辑关系），即数据的（逻辑结构）。
3.数据的逻辑结构可形式的用一个二元组B=(K,R)来表示，其中K表示（数据元素的集合），R表示（关系的集合）。
4.数据元素之间的关系有四种基本的存储表示方法即，（顺序存储），（链式存储），（索引存储），（散列存储）。
5.数据的集中运算中，（创建）是一个很重要的运算过程，插入，删除，修改，排序都包含着这种运算。
1、线性表示一种最简单、常用的数据结构，通常一个线性表由n个性质相同的数据元素组成的（一个有限序列），其长度即为线性表中元素的个数n，当n=0时，称（空表）。
2、线性表是一种（顺序存储）结构。
3、线性表的顺序存储有哪些特点？1.、元素特性相同2、线性结构3、元素个数n>=0
4、线性表的链式存储有哪些特点？
5、如果线性表中最常用的操作是存取第I个元素及其前驱的值，则采用（顺序）存储方式节省时间。
5、线性表的两种存储结构其中（顺序）存储密度较大；（顺序）存储利用率较高；（链式）可以随机存取；（顺序）不可以随机存取；（链式）插入和删除操作比较方便。
6、什么叫直接前驱元素，什么叫直接后继元素？
1、栈是限定仅在（一端）进行插入删除操作的线性表。允许进行插入删除的一端为（栈顶），另一端为（栈底）。
2、栈的运算有（进栈）、（出栈）、（）、（初始化栈）和（销毁栈）。
3、栈有两种存储表示方法：（顺序栈）和（链栈）。
4、队列只允许在一端进行（插入），在另一端（删除）。
5、队尾指（进行插入元素的一端），对头指（进行删除元素的一端）。
6、设栈S和队列Q的初始状态皆为空，元素a，b，c，d，e，f依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素的出队列的顺序是c，e，d，f，b，a则栈S至少应该容纳（3）个元素。
7、栈和队列的逻辑结构都是（链式存储）。
8、如果某栈的初始为空，push和pop分别表示对堆栈进行一次进栈与出栈操作，那么，对于输入序列a,b,c,d,e,依次经过push,push,pop,push,pop,push,push，pop以后，输出序列应该是（bceda）。
9、一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列的是（b）
a、2，3，4，1，5 b 、5，4，1，3，2
c 、2，3，1，4，5 d、1，5，4，3，2
10、对于下面的每一步画出栈中元素及栈顶指针的示意图。
空栈；元素a入栈；元素b入栈；删除栈顶元素；元素c入栈；删除栈顶元素。
11、比较栈和队列的相同点不同点。
12、若依次输入数据元素序列a,b,c,d,e,f,g进栈，出栈操作可以和入栈操作间隔进行，则下列哪些元素序列可以由出栈序列得到。2
1、d,e,c,f,b,g,a
2、f,e,g,d,a,c,b
3、e,f,d,g,b,c,a
4、c,d,b,e,f,a,g
13、将整数1，2，3，4依次入栈，如果push(1),pop( ),push(2),push(3),pop( ),pop( ),push(4),pop( ),则出栈的数字序列为（1324）。试分析1，2，3，4的24种排列中，哪些序列不能通过相应的入出栈得到。
1、串是（由零个或多个字符组成的有限序列）。
2、空串是指（含有零个字符的串）。
3、如何判断一个串是另外一个串的子串。
4、如何判断两个串相等。
5、串有哪两种存储方式。
6、串的长度是指（串中元素的个数）。
7、空串与空格串的区别是什么？
1、已知一维数组Ａ采用顺序存储结构，每个元素占４个存储单元，如果第一个元素的地址为100，则A[10]的地址是140；如果第九个元素的地址为144，则该数组的首地址是108。
2、数组是有一组（n个相同类型）的数据元素构成的（有限序列），且（该序列存储在一块连续的内存空间中）。
3、数组具有哪些性质？数组中数据元素数目固定，数据元素具有相同的类型，数组中的每个元素和一组唯一的下标值对应，数组是一组随机存储结构，可以随机存储数组中的任意元素。
4、什么叫表头，什么叫表尾？第一个元素为表头，最后一个元素为表尾
5、广义表有哪些特点？广义表中的数据元素具有相对次序，广义表的长度为最外层包含元素的个数，其深度包含弧的重数。
6、取出广义表：LS=(a,b,(c,d,e),(f,g))
元素c的操作是（广义表的子表的原子）。
7、求下列广义表的运算结果：
HEAD((p,h,w),(a,b,c)); TAIL((b,k,p,h),(b,c));
8、如何求广义表的长度和深度。
1、树的概念是什么。N个节点组成的有限序列
2、子树的概念。每一棵树的子集
3、从树的定义可以看出树具有哪两个特点。每一个节点可以有零个或多个直接后继，但只有一个直接前驱（根节点除外），反应了数据元素之间的关系。
4、树的表示方法有（树形表示）、（文氏图表示）、（括号表示）。
5、二叉树是（二分树）。
6、满二叉树是指（所有节点都有左右孩子结点，并且叶子节点都在二叉树的最下一层）。
7、完全二叉树是指（最多只有最下面两层的节点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上）。
8、二叉树的性质有哪些？
9、如何计算树的带全路径的长度
1、图是一种数据结构，它的形式化定义为Graph=(V,E)其中V是（顶点的有限集合），E 是（连接V中两个不同顶点的边的有限集合）。
2、无向图是（边的顶点对是无序的），有向图是（边的顶点对是有序的）。
3、图的深度优先搜索的遍历过程类似于树的（先序遍历）。
4、图的广度优先搜索的遍历过程类似于树的（层次遍历）。
5、什么叫关键路径？
6、P222页图8-31试有向连通图么？求顶点A到其他各顶点的最短路径，及最短路径的长度
1、什么叫关键字？
2、顺序查找也称（），它属于（静）态查找。
1、排序是将一组记录按照记录中的某个（关键字）进行有序排列的过程。
2、下列排序方法中，那种方法的比较次数与记录的初始排列状态无关（d ）。
a、直接插入排序
b、起泡排序
c、快速排序
d、直接选择排序
3、已知序列35，78，12，26，90，41，66，58，请写出对该序列分别采用直接插入排序、冒泡排序方法进行升序排序时各趟的结果。
1、文件是（存放在外存上，有名、有类别的相关信息的集合）。
2、磁带是一种（顺序）存储设备。
3、剪贴板用来存放需立即使用的程序和数据，它可以直接访问CPU。
4、文件的操作主要有：保存、移动、删除、和排序
《数据结构》填空作业题答案
《数据结构》填空作业题答案 第1章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S）。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7. 在树形结构中，数据元素之间存在一对多的关系。 8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9. 数据的逻辑结构包括线性结构、树形结构和图形结构 3种类型，树型结构和有向图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。 12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14. 数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。 16. 数据元素可由若干个数据项组成。 17. 算法分析的两个主要方面是时间复杂度和空间复杂度。 18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 n 。 21. 下面程序段的时间复杂度为㏒ 3
电大考试数据结构(本)试题集附答案
数据结构（本）期末综合练习 2017年5月 有得看就不难 综合练习一 一、单项选择题 1．设有头指针为head的带有头结点的非空单向循环链表, 指针p指向其尾结点, 要删除头结点,并使其仍为单向循环链表,则可利用下述语句head =head->next ;（）。 A．p =head; B．p=NULL; C．p->next =head; D．head=p; 2．在一个单链表中p指向结点a, q指向结点a的直接后继结点b，要删除结点b，可执 行（）。 A．p->next=q->next ; B．p=q->next; C．p->next=q; D．p->next=q; 3. 以下说法不正确的是 A. 线性表的链式存储结构不必占用连续的存储空间 B．一种逻辑结构只能有唯一的存储结构 C. 一种逻辑结构可以有不同的存储结构 D．线性表的顺序存储结构必须占用连续的存储空间 4．在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行（）;和 p->next=s; A．p= s; B． p->next=s->next; C．p=s->next; D． s->next=p->next; 5．把数据存储到计算机中，并具体体现( )称为物理结构。 A. 数据元素间的逻辑关系 B．数据的处理方法 C．数据的性质 D．数据的运算 6．设有一个长度为23的顺序表，要删除第8个元素需移动元素的个数为（）。 A．16 B．14 C．15 D．13 7．链表所具备的特点之一是（）。 A．可以随机访问任一结点 B．需要占用连续的存储空间 C．插入元素的操作不需要移动元素 D．删除元素的操作需要移动元素 8．设一棵有8个叶结点的二叉树，度数为1的结点有3个,则该树共有（）个结点。 A．20 B．18 C．17 D．16 9．图状结构中数据元素的位置之间存在（）的关系。 A．一对一 B．多对多 C．一对多 D．每一个元素都有一个直接前驱和一个直接后继10．一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。 A．14 B．15 C．19 D．18 11．元素15，9，11，13按顺序依次进栈，则该栈的不可能输出序列是（） （进栈出栈可以交替进行）。 A．13，11，9，15 B．15，9，11，13 C．13，11，15，9 D．9， 15，13，11 1
(完整版)数据结构练习题(含答案)
数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 1、数据结构按结点间的关系，可分为4种逻辑结构： 集合、线性结构、树形结构、图状结构。 2、数据结构中的数据元素存在多对多的关系称为图 状结构结构。 3、在一个长度为n的顺序存储结构的线性表中，向第 i(1≤i≤n+1)个元素之前插入新元素时，需向后移动n-i+1个数据元素。 4、从长度为n的采用顺序存储结构的线性表中删除第 i(1≤i≤n+1)个元素，需向前移动n-i个元素。5、数据的逻辑结构在计算机中的表示称为物理结构 或存储结构。 6、除了第1个和最后一个结点外，其余结点有且只有一 个前驱结点和后继结点的数据结构为线性结构，每个结点可有任意多个前驱和后继结点数的结构为非线性结构。 7、算法的5个重要特性是有穷性、确定性、可形 性、有零个或多个输入、有零个或多个输出。 8、数据结构中的数据元素存在一对多的关系称树 形结构结构。 9、往栈中插入元素的操作方式是：先移动栈顶指针， 后存入元素。 10、数据结构中的数据元素存在一对一的关系称为线 性结构结构。 11、要求在n个数据元素中找其中值最大的元素，设基本 操作为元素间的比较。则比较的次数和算法的时间复杂度分别为n-1和O(n)。 12、在一个单链表中p所指结点之后插入一个s所指结点 时，应执行__s->next=p->next;__和p->next=s;的操作。 13、设有一个头指针为head的单向循环链表，p指向链 表中的结点，若p->next= =head，则p所指结点为尾结点。 14、在一个单向链表中，要删除p所指结点，已知q指向 p所指结点的前驱结点。则可以用操作q->next=p->next; 。 15、设有一个头指针为head的单向链表，p指向表中某 一个结点，且有p->next= =NULL,通过操作p->next=head;,就可使该单向链表构造成单向循环 链表。 16、每个结点只包含一个指针域的线性表叫单链表。 17、线性表具有顺序存储和链式存储两种 存储结构。 18、数据的逻辑结构是从逻辑关系上描述数据，它与数据 的关系存储结构无关，是独立于计算机的。19、在双向循环链表的每个结点中包含两个指针域，其 中next指向它的直接后继，prior指向它的直接前驱，而头结点的prior指向尾结点，尾结点的next指向头结点。 20、单向循环链表是单向链表的一种扩充，当单向链表带 有头结点时，把单向链表中尾结点的指针域由空指针改为头结点的指针；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向指向第一个结点的指针。 21、线性链表的逻辑关系时通过每个结点指针域中的指 针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种链式存储结构，又称为链表。 22、栈是限定在表的一端进行插入和删除操作的线性表， 又称为后进先出表。 23、队列的特性是先进先出表。 24、删除栈中元素的操作方式是：先取出元素，后移 动栈顶指针。 25、循环队列队头指针在队尾指针下一个位置，队列是 “满”状态 26、在队列的顺序存储结构中，当插入一个新的队列元素 时，尾指针增1 ，当删除一个元素队列时，头指针增1。 27、循环队列的引入，目的是为了克服假上溢。 28、向顺序栈插入新元素分为三步：第一步进行栈是否 满判断，判断条件是s->top=MAXSIZE-1 ；第二步是修改栈顶指针；第三步是把新元素赋给栈顶对应的数组元素。同样从顺序栈删除元素分为三步：第一步进行栈是否空判断，判断条件是s->top=-1。第二步是把栈顶元素；第三步修改栈顶指针。 29、假设以S和X分别表示入栈和出栈操作，则对输入序 列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为bceda。 "题目1：把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。: 逻辑结构 ; 算法的具体实现 ; 给相关变量分配存储单元 ; 物理结构" "题目2：下列说法中，不正确的是（）。 : 数据元素是数据的基本单位 ; 数据项可由若干个数据元素构成 ; 数据项是数据中不可分割的最小可标识单位 ; 数据可有若干个数据元素构成" "题目3：一个存储结点存储一个（）。 : 数据类型 ; 数据元素 ; 数据结构 ; 数据项" "题目4：数据结构中，与所使用的计算机无关的是数据的（）。 : 物理结构 ; 逻辑结构 ; 存储结构 ; 物理和存储结构" "题目5：在线性表的顺序结构中，以下说法正确的是（）。 : 数据元素是不能随机访问的 ; 逻辑上相邻的元素在物理位置上也相邻 ; 进行数据元素的插入、删除效率较高 ; 逻辑上相邻的元素在物理位置上不一定相邻" "题目6：对链表, 以下叙述中正确的是（）。 : 插入删除元素的操作一定要要移动结点 ; 不能随机访问任一结点 ; 可以通过下标对链表进行直接访问 ; 结点占用的存储空间是连续的" "题目7：下列的叙述中，不属于算法特性的是（）。 : 输入性 ; 可读性 ; 可行性 ; 有穷性" "题目8：算法的时间复杂度与（）有关。 : 数据结构 ; 计算机的操作系统 ; 所使用的计算机 ; 算法本身" "题目9：设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。 : n-i+1 ; n-i-1 ; i ; n-i" "题目10：设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。 : n-i-1 ; n-i ; i ; n-i+1" "题目11：在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。 : p->next=q->next ; q->next=NULL ; p->next=q ; p=q->next" "题目12：在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。 : s->next=p->next; p->next=s; ; p->next=s->next; ; p->next= s; s->next= p->next ; p=s->next" "题目13：非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。 : p== head ; p->next==NULL ; p->next==head ; p==NULL" "题目14：链表不具有的特点是（）。 : 插入删除不需要移动元素 ; 不必事先估计存储空间 ; 逻辑上相邻的元素在物理位置上不一定相邻 ; 可随机访问任一元素" "题目15：带头结点的链表为空的判断条件是（）（设头指针为head）。 : head->next==head ; head->next==NULL ; head!=NULL ; head ==NULL" "题目16：在一个长度为n的顺序表中为了删除第5个元素，由第6个元素开始从后到前依次移动了15个元素。则原顺序表的长度为（）。 : 19 ; 21 ; 25 《数据结构-C语言版》 第一章绪论 单项选择题 1．在数据结构中，数据的基本单位是_____ ____。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL 习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 《数据结构》程序填空复习题 说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题，黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。不能放弃其他内容的复习，切记！！！ 一、线性表 1.设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 #define NULL 0 void main( ) {NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16; d.data=4; /*d是尾结点*/ head= （1）; a.next=&b; b.next=&c; c.next=&d; （2）; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do {printf(“%d\n”, （3）); （4）; }while( （5）); } 答案： （1）&a （2）d next=NULL （3）p->data （4）p=p->next （5）p!=NULL 2. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点， struct node { int data; struct node *next; }; typedef struct node NODE int delete(NODE *head,int i ) { NODE *p,*q; int j; q=head; j=0; while((q!=NULL)&&( ___(1)_____)) { ___(2)_____; j++; } if(q==NULL) return(0); p= ___(3)_____; ___(4)_____=p->next; free(___(5)_____); return(1); } 答案： （1）j 习题一 一、填空题 1. 算法具有有穷性、确定性、可行性、输入和输出五大特征。 2. 数据结构的内容包括以下三个方面：数据元素、数据关系和运算集合。 3. 数据结构的存储结构分为顺序、链式、索引、散列。 4. 评价算法性能的标准主要从算法执行时间和空间两方面考虑。 5. 在线性结构、树形结构和图状结构中，数据元素之间分别存在着1对1 、1对多和多对多关系。 二、分析题 2.设n为整数，分析下列程序段中，用*标明的语句的语句频度及时间复杂度。（1）for(n =1;n<=10;n++) *s=s+n; (2) for(i =1;i<=n;i++) *s=s+n; (3) for(i =1;i<=n;i++) for(j=1;j<=n;j++) *s=s+n (4) for(i =1;i<=n;i++) for(j=1;j<=i ;j++) *s=s+n; （5）for(i =1;i<=n;i++) for(j=1;j<=n;j++) { c[i][j]=0; for(k=1;k<=n;k++) *c[i][j]=c[i][j]+a[i][k]*b[k][j]; } 习题二 3.填空题 1.在顺序表中，逻辑上相邻的元素，其物理位置上一定相邻。 2.在单链表中，逻辑上相邻的元素，其物理位置上不一定相邻。 3.设单链表中，指针p指向结点s，若要删除s之后的结点（若存在），则需修改指针的操作为P=s->next;s->next=s->next->next;free(p); 。 4.在一个长度为n的顺序表中，如果要删除第i个元素，需移动n-i+1 个元素。 二、选择题 1.某线性表中最常用的操作是存取序号为i的元素和在最后进插入和删除运算，则采用（C ）存储方式的时间性能最好。 A.双向链表 B.双向顺环链表 C.顺序表 D.单向顺环链表 2.在一个单链表中，已知q结点是p结点的前驱结点，若在p和q之间插入s结点，则需执行（ C ）。 A.s->next=p->next;p->next=s B.p->next=s->next;s->next=p C.q->next=s;s->next=p D.p->next=s;s->next=q 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 数据结构习题 习题一绪论 .1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。 ①A．操作对象Ｂ．计算方法Ｃ．逻辑存储Ｄ．数据映象 ②A．结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②有限集合。 ①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．逻辑结构 ②A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成①。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 线性表的顺序存储结构是一种①的存储结构，线性表的链式存储结构是一种②的存储结构。 A．随机存取B．顺序存取C．索引存取D．散列存取 5. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 6. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 7. 线性表的逻辑顺序与存储顺序总是一致的，这种说法①。 A. 正确 B. 不正确 8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址①。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 9. 在以下的叙述中，正确的是①。 A.线性表的线性存储结构优于链表存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 10. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法①。 A. 正确 B. 不正确 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括①、②和③三种类型，树形结构和图形结构合称为④。 集合、线性结构、树型结构非线性结构 2. 在线性结构中，第一个结点①前驱结点，其余每个结点有且只有②个前驱结点；最后一个结点③后续结点，其余每个结点有且只有④个后续结点。 无、一、无、一 3. 在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点，叶子结点没有③结点，其余每个结点的后续结点可以④。 前驱、一、后继、零个至多个 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以①。 任意多个 5. 线性结构中元素之间存在①关系，树形结构中元素之间存在②关系，图形结构中元素之间存在③关系。 一对一、一对多、多对多 6. 算法的五个重要特性是 7. 下面程序段的时间复杂度是①。 for (i=0;i 栈和队列 3.1 单项选择题 1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。 A. i B. n=i C. n-i+1 D. 不确定 3. 栈结构通常采用的两种存储结构是。 A.顺序存储结构和链式存储结构 B. 散列方式和索引方式 C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 4. 判定一个顺序栈ST（最多元素为m0）为空的条件是。 A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-1 5. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是。 A. top！=0 B. top= =0 C. top！=m0 D.top= =m0-1 6. 栈的特点是 B ，队列的特点是 A 。 A. 先进先出 B. 先进后出 7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。 (不带空的头结点) A. HS—＞next=s; B. s—＞next= HS—＞next; HS—＞next=s; C. s—＞next= HS; HS=s; D. s—＞next= HS; HS= HS—＞next; 8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。(不带空的头结点) A. x=HS; HS= HS—＞next; B. x=HS—＞data; C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞next; 9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1 10. 判定一个循环队列QU（最多元素为m0）为空的条件是。 A. rear - front= =m0 B. rear-front-1= =m0 C. front= = rear D. front= = rear+1 11. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是。 A. ((rear- front)+ Maxsize)% Maxsize = =m0 B. rear-front-1= =m0 C. front= =rear D. front= = rear+1 12. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。 A. (rear-front+m)%m B. rear-front+1 电大数据结构（本）考核作业答案 作业1 一、单项选择题 1．C 2．D 3．B 4．C 5．D 6．C 7．B 8．C 9．A 10．B 11．C 12．D 13．C 14．A 15．B 16．C 17．C 18．B 19．B 20．D 二、填空题 1．n-i+1 2．n-i 3．集合线性结构树形结构图状结构 4．物理结构存储结构 5．线性结构非线性结构 6．有穷性确定性可形性有零个或多个输入有零个或多个输出 7．图状结构 8．树形结构 9．线性结构 10．n-1 O(n) 11．s->next=p->next; 12．head 13．q->next=p->next; 14．p->next=head; 15．单链表 16．顺序存储链式存储 17．存储结构 18．两个直接后继直接前驱尾结点头结点 19．头结点的指针指向第一个结点的指针 20．链式链表 三、问答题 1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？ 答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。 2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。 答： 顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。 缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间， 数据结构课程平时作业1 一．单项选择题 1．数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。 ①A．操作对象B．计算方法C．逻辑存储D．数据映象 ②A．结构B．关系C．运算D．算法 2．数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②的有限集合。 ①A．算法B．数据元素C．数据操作D．逻辑结构 ②A．操作B．映象C．存储D．关系 3．在数据结构中，从逻辑上可以把数据结构分成( )。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 4. 线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 5. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储 二.填空题（将正确的答案填在相应的空中） 1．在线性结构中，第一个结点①前驱结点，其余每个结点有且只有②个前驱结点；最后一个结点③后续结点，其余每个结点有且只有④个后续结点。 2．在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后续结点可以④。 3．在图形结构中，每个结点的前驱结点数和后续结点数可以①。 4．线性结构中元素之间存在①关系，树形结构中元素之间存在②关系，图形结构中元素之间存在③关系。 5. 数据结构包括数据的、数据的和数据的这三个方面的内容。6．下面程序段的时间复杂度是①。 for（i=0；i＜n；i++） for（j=0；j＜m；j++） A[i][j]=0； 7．下面程序段的时间复杂度是①。 S＝0； 数据结构程序填空题 Last revision date: 13 December 2020. 数据结构程序填空题S设有一个头指针为head的不带头结点单向链表, 且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点 a的数据域相同）, 写出相关语句 答案 （1）q->next=head;（2）p=p->next;（3）q->next=p->next; 设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中结点a, （设链表中没有结点的数据域与结点a 的数据域相同）,写出相关语句 答案：（1）q->next=head (2) p=p->next; （3）q->next=p->next 设有一个不带头结点的单向链表，头指针为head，p、prep是指向结点类型的指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序 段是在该单向链表中查找这相邻两个结点，把该结点的数据域data打印 出来，并把其中之一从链表中删除，填写程序中的空格。 （1）p=p->next;（2）p->data或prep->data（3）p->next 设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表， 并输出链表中各结点中的数据。 答案：（1）&a（2）（3）p->data（4）p=p->next（5）p!=NULL 设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data。 答案：（1）p->data（2）p=p->next（3）p!=NULL 设线性表为（1，3，7，5），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 答：（1）&a（2）d->next=NULL（3）p->data（4）p=p->next（5）P指向NULL X 学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到n-1。数组元素按学号num由小到大有序排列，以下函数在a[0]到a[n-1] 中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记录的下标（数组元素的下标）。失败时返回-1，完成程序中的空格。 （1）low<=high（2）mid（3）a[mid].num 数据结构习题 一、名词解释 1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、 算法、时间复杂度、空间复杂度。 2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头 指针、头结点、首元结点（第1个元素结点）。 3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。 4. 树、叶子结点、结点的度、树的度、树的高（深）度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL哈夫曼编码。 5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、 （最小）生成树、邻接矩阵、邻接表、DFS BFSO 6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。 7. 排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2 路归并。 一、填空题 1. 数据结构是研究数据的 _逻辑结构_和—物理结构_ ,并在这种结构上定义相关的运算，设计实 现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为—时间复杂度和空间复杂度—。 2. 数据的基本单位是数据元素，数据的最小单位是数据项。 3. 算法是对特定问题求解—步骤___的一种描述，是指令的有限序列。 4. 一个算法的时间复杂度为（3n3+2n — 7）,其数量级表示为_0 （ n3） __。 5. 一个算法具有5个特性：_确定性、—可行性_、_有穷性_、输入和输出。 6. 算法性能的分析和度量，可以从算法的时间复杂度一和—空间复杂度—来评价算法的优劣。 7. 数据的逻辑结构包括集合结构、_线性结构 _、—树形结构_和_图型结构—四种类型。 8. 数据结构在计算机中的表示称为数据的物理结构，它可以采用 _顺序存储_ 或_链式存储_ 两种存储方法。 9. 线性表有两种存储结构，分别为_顺序存储 _ 和___________ 链式存储_。 10. 链式存储的特点是利用指针—来表示数据元素之间的逻辑关系。 11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用链式存储—存储结构。 12. 线性表中的数据元素之间具有 _一对一_的线性关系，除第一个和最后一个元素外，其他数据元素有且只有 一个_直接后继和直接前趋。 13. 在一个单链表中 P所指结点之后插入一个S所指结点时，应执行 s->next=_ p->next ___________ 和 p->next=_ S ________ 的操作。 中央电大计算机科学与技术专业 数据结构（本科）试卷7 2003年7月已考 一、选择题（每小题1分，共10分） 1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 2.带头结点的单链表first为空的判定条件是： A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 3.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为 对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。 A. 空间 B. 副本 C. 返回地址 D. 地址 5.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. –1 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长 度为（）的值除以9。 A. 20 B. 18 C. 25 D. 22 8.在有向图中每个顶点的度等于该顶点的（）。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差 9.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 10.当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。 A. 较慢 B. 较快 C. 相同 二、填空题（每小题1分，共10分） 1.二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或 直接后继）。开放大学数据结构2020年考试必备填空题
电大数据结构(本)形考作业1-阶段性学习测验1答案
数据结构复习题目和答案
数据结构习题及参考答案 .
《数据结构》程序填空复习题
数据结构习题
数据结构试题答案
数据结构课后练习题
数据结构复习题
电大数据结构形成性考核册答案(作业1-4)
2020年国家开放大学电大数据结构题库
数据结构程序填空题
数据结构复习题及答案
中央电大计算机科学与技术专业数据结构(本科)试卷7