文档库 最新最全的文档下载
当前位置:文档库 › 自考数据结构复习公式

自考数据结构复习公式

自考数据结构复习公式
自考数据结构复习公式

(1)按行优先顺序存储的二维数组Amn地址计算公式

LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d

其中:①LOC(a11)是开始结点的存放地址(即基地址)

②d为每个元素所占的存储单元数

③由地址计算公式可得,数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。(2)按列优先顺序存储的二维数组Amn地址计算公式

LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d

(3)按行优先顺序存储的三维数组Amnp地址计算公式

LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d

(4)下界不为1的二维数组的地址计算公式

①二维数组A[c1..d1,c2..d2]的地址计算公式:

LOC(aij)=LOC(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d

②下界为0的二维数组的地址计算公式(C语言中使用)

LOC(aij)=LOC(a00)+[i×(d2+1)+j]×d

②元素aij的存放位置

aij元素前有i行(从第0行到第i-1行),一共有:1+2+…+i=i×(i+1)/2个元素;

在第i行上,aij之前恰有j个元素(即ai0,ail,…,ai,j-1),因此sa[i×(i+1)/2+j]= aij

③aij和sa[k]之间的对应关系:

若i≥j,k=i×(i+1)/2+j 0≤k

若i<j,k=j×(j+1)/2+i 0≤k

令I=max(i,j),J=min(i,j),则k和i,j的对应关系可统一为:k=i×(i+1)/2+j 0≤k

(3)对称矩阵的地址计算公式

LOC(aij)=LOC(sa[k])

=LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)/2+J]×d

①E()

②L(a,b)

③A(x,L(a,b))

④B(A(x,L(a,b)),y)

⑤C(A(x,l(a,b)),B(A(x,L(a,b)),y))

⑥D(a,D(a,D(…)))

②广义表的两个特殊的基本运算:取表头head(Ls)和取表尾tail(Ls)。

二叉树第i层上的结点数目最多为2i-1(i≥1)。

深度为k的二叉树至多有2k-1个结点(k≥1)。

在任意-棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则no=n2+1。

具有n个结点的完全二叉树的深度为

完全二叉树中除最下面一层外,各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲,左、右孩子,兄弟等结点的编号。假设编号为i的结点是ki(1≤i≤n),则有:

①若i>1,则ki的双亲编号为;若i=1,则Ki是根结点,无双亲。

②若2i≤n,则Ki的左孩子的编号是2i;否则,Ki无左孩子,即Ki必定是叶子。因此完全二叉树中编号的结点必定是叶结点。

③若2i+1≤n,则Ki的右孩子的编号是2i+1;否则,Ki无右孩子。

④若i为奇数且不为1,则Ki的左兄弟的编号是i-1;否则,Ki无左兄弟。

⑤若i为偶数且小于n,则Ki的右兄弟的编号是i+1;否则,Ki无右兄弟。

中序是一种对称序,故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继结点的方法完全对称。具体情形如下:

①若*p的左子树为空,则p->1child为左线索,直接指向*p的中序前趋结点;

②若*p的左子树非空,则从*p的左孩子出发,沿右指针链往下查找,直到找到一个没有右孩子的结点为止。该结点是*p的左子树中"最右下"的结点,它是*p的左子树中最后一个中序遍历到的结点,即*p的中序前趋结点。

在中序线索二叉树中,查找结点*p的中序后继结点分两种情形:

①若*p的右子树空(即p->rtag为Thread),则p->rchild为右线索,直接指向*p的中序后继。

③若*p的右子树非空(即p->rtag为Link),则*p的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p的右孩

子开始,沿该孩子的左链往下查找,直至找到一个没有左孩子的结点为止,该结点是*p的右子树中"最左下"的结点,即*P的中序后继结点。

序线索二叉树中,查找指定结点*p的后序前趋结点

在后序线索二叉树中,查找指定结点*p的后序前趋结点的具体规律是:

①若*p的左子树为空,则p->lchild是前趋线索,指示其后序前趋结点。

②若*p的左子树非空,则p->lchild不是前趋线索。由于后序遍历时,根是在遍历其左右子树之后被访问的,故*p的后序前趋必是两子树中最后一个遍历结点。

当*p的右子树非空时,*p的右孩子必是其后序前趋

在后序线索二叉树中,查找指定结点*p的后序后继结点

具体的规律:

①若*p是根,则*p是该二叉树后序遍历过程中最后一个访问到的结点。*p的后序后继为空

②若*p是其双亲的右孩子,则*p的后序后继结点就是其双亲结点

③若*p是其双亲的左孩子,但*P无右兄弟,*p的后序后继结点是其双亲结点

④若*p是其双亲的左孩子,但*p有右兄弟,则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点,它是该子树中"最左下的叶结点"

树转换成相应的二叉树:

①在所有兄弟结点之间加一连线;

②对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。

将一个森林转换为二叉树具体方法是:

①将森林中的每棵树变为二叉树

②因为转换所得的二叉树的根结点的右子树均为空,故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。

把二叉树转换到树和森林自然的方式是:若结点x是双亲y的左孩子,则把x的右孩子,右孩子的右孩子,…,都与y用连线连起来,最后去掉所有双亲到右孩子的连线。

1.前序遍历森林

若森林非空,则:

①访问森林中第一棵树的根结点;

②前序遍历第一棵树中根结点的各子树所构成的森林

③前序遍历除第一棵树外其它树构成的森林。

2.后序遍历森林

若森林非空,则:

①后序遍历森林中第一棵树的根结点的各子树所构成的森林;

②访问第一棵树的根结点;

③后序遍历除第一棵树外其它树构成的森林。

注意:

①前序遍历森林等同于前序遍历该森林对应的二叉树

②后序遍历森林等同于中序遍历该森林对应的二叉树

③当用二叉链表作树和森林的存储结构时,树和森林的前序遍历和后遍历,可用二叉树的前序遍历和中序遍历算法来实现。(1)平方阶(O(n2))排序一般称为简单排序,例如直接插入、直接选择和冒泡排序;

(2)线性对数阶(O(nlgn))排序如快速、堆和归并排序;

(3)O(n1+£)阶排序£是介于0和1之间的常数,即0<£<1,如希尔排序;

(4)线性阶(O(n))排序如桶、箱和基数排序。

简单排序中直接插入最好,快速排序最快,当文件为正序时,直接插入和冒泡均最佳。

自考数据结构导论复习资料

数据结构导论复习 第一章概论 1.数据:凡能被计算机存储、加工处理的对象。 2.数据元素:是数据的基本单位,在程序中作为一个整体而加以考虑和处理 3.数据项:又叫字段或域,它是数据的不可分割的最小标识单位。 4.逻辑结构需要注意的几点: ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5.数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6.四类基本逻辑结构(集合、线性结构、树形结构和图形结构)的不同特点? 答:集合中任何两个结点之间都没有逻辑关系,组织形式松散; 线性结构中结点按逻辑关系依次排列形成一条“锁链”; 树形结构具有分支、层次特性,其形态有点像自然界中的树; 图状结构最复杂,其中的各个结点按逻辑关系互相缠绕,任何两个结点都可以领接。 7.运算是在逻辑结构层次上对处理功能的抽象

8.基本运算的含义? 答:假如是S上的一些运算的集合,是的一个子集,使得中每一运算都可以“归约”为中的一个或多个运算,而中任一运算不可归约为别的运算,则称中运算为基本运算 9.数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体(S ,)。 10.数据结构涉及数据表示和数据处理两个方面 11.存储结构的含义和四种基本存储方式的基本思想? 答:存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分:存储结点、机内表示和附加设施。 存储结构包括四种存储方式,顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12.运算实现与运算的联系与区别? 答:运算指的是数据在逻辑结构S上的某种操作,运算只描述处理功能,不包括处理步骤和方法;而运算实现是指一个完成该运算功能的程序,运算实现的核心是处理步骤的规定,即算法设计。 13.算法的概念和分类? 答:算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序,使得给定类型的任何问题能在有限时间内被

自考数据结构试题真题

全国2011年1月高等教育自学考试 数据结构试题 课程代码:02331 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是() A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是() A.n-1 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为m,队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置,则向队列中插入新元素时,修改指针的操作是() A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时,处理参数及返回地址,应采用的数据结构是() A.堆栈 B.多维数组 C.队列 D.线性表 5.设有两个串p和q,其中q是p的子串,则求q在p中首次出现位置的算法称为() A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表A,若head(A)等于tail(A),则表A为() A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反,则该二叉树一定是 ()A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树

C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3,度为2的结点个数是4,则该二叉树叶子结点的个数是() A.4 B.5 C.7 D.8 9.下列叙述中错误的是() A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10.已知有向图G=(V,E),其中V={V1,V2,V3,V4},E={},图G的拓扑序列是() A.V1,V2,V3,V4 B.V1,V3,V2,V4 C.V1,V3,V4,V2 D.V1,V2,V4,V3 11.平均时间复杂度为O(n log n)的稳定排序算法是() A.快速排序 B.堆排序 C.归并排序 D.冒泡排序 12.已知关键字序列为(51,22,83,46,75,18,68,30),对其进行快速排序,第一趟划分完成后的关键字序列是() A.(18,22,30,46,51,68,75,83) B.(30,18,22,46,51,75,83,68) C.(46,30,22,18,51,75,68,83) D.(30,22,18,46,51,75,68,83) 13.某索引顺序表共有元素395个,平均分成5块。若先对索引表采用顺序查找,再对块中元素进行顺序查找,则在等概率情况下,分块查找成功的平均查找长度是()A.43 B.79 C.198 D.200 14.在含有10个关键字的3阶B-树中进行查找,至多访问的结点个数为() A.2 B.3 C.4 D.5 15.ISAM文件系统中采用多级索引的目的是() A.提高检索效率 B.提高存储效率

计算机系统结构重点题解自考复习资料

第 1 章计算机系统结构的基本概念 1.1 解释下列术语 层次结构:按照计算机语言从低级到高级的次序,把计算机系统按功能划分成多级层次结构,每 一层以一种不同的语言为特征。这些层次依次为:微程序机器级,传统机器语言机器级, 汇编语言机器级,高级语言机器级,应用语言机器级等。 虚拟机:用软件实现的机器。 然后再在这低翻译:先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序, 一级机器上运行,实现程序的功能。 解释:对于高一级机器上的程序中的每一条语句或指令,都是转去执行低一级机器上的一段等效 程序。执行完后,再去高一级机器取下一条语句或指令,再进行解释执行,如此反复, 直到解释执行完整个程序。 计算机系统结构:传统机器程序员所看到的计算机属性,即概念性结构与功能特性。 在计算机技术中,把这种本来存在的事物或属性,但从某种角度看又好像不存在的概念称为透 明性。 计算机组成:计算机系统结构的逻辑实现,包含物理机器级中的数据流和控制流的组成以及逻 辑设计等。 计算机实现:计算机组成的物理实现,包括处理机、主存等部件的物理结构,器件的集成度和速度,模块、插件、底板的划分与连接,信号传输,电源、冷却及整机装配技术等。 系统加速比:对系统中某部分进行改进时,改进后系统性能提高的倍数。 Amdahl 定律:当对一个系统中的某个部件进行改进后,所能获得的整个系统性能的提高, 受限于该部件的执行时间占总执行时间的百分比。 而是相对地簇聚。包程序的局部性原理:程序执行时所访问的存储器地址不是随机分布的, 括时间局部性和空间局部性。 CPI:每条指令执行的平均时钟周期数。 测试程序套件:由各种不同的真实应用程序构成的一组测试程序,用来测试计算机在各个方面的 处理性能。

2021年自学考试数据结构重点总结02331整理

自考数据构造重点(整顿) 第一章概论 1.瑞士计算机科学家沃思提出:算法+数据构造=程序。算法是对数据运算描述,而数据构造涉及逻辑构造和存储构造。由此可见,程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法,而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成,数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系,即数据组织形式。 数据构造普通涉及如下三方面内容:数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据,与数据元素存储构造无关,是独立于计算机。 数据逻辑构造分类:线性构造和非线性构造 ②数据元素及其关系在计算机内存储方式,称为数据存储构造(物理构造)。 数据存储构造是逻辑构造用计算机语言实现,它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法:顺序存储、链接存储、索引存储、散列存储 (1)顺序存储:普通借助程序设计语言数组描述。 (2)链接存储:普通借助于程序语言指针来描述。 (3)索引存储:索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 (4)散列存储:该办法基本思想是:依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则:输入,0个或各种数据作为输入;输出,产生一种或各种输出;有穷性,算法执行有限步后结束;拟定性,每一条指令含义都明确;可行性,算法是可行。 算法与程序区别:程序必要依赖于计算机程序语言,而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类:类Pascal和类C。 6.评价算法优劣:算法"对的性"是一方面要考虑。此外,重要考虑如下三点: ①执行算法所耗费时间,即时间复杂性; ②执行算法所耗费存储空间,重要是辅助空间,即空间复杂性; ③算法应易于理解、易于编程,易于调试等,即可读性和可操作性。 以上几点最重要是时间复杂性,时间复杂度惯用渐进时间复杂度表达。

自考02331数据结构重点总结(最终修订)

自考02331数据结构重点总结(最终修订) 第一章概论 1.瑞士计算机科学家沃思提出:算法+数据结构=程序。算法是对数据运算的描述,而数据结构包括逻辑结构和存储结构。由此可见,程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构。 2.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成,数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。 3.数据结构指的是数据元素之间的相互关系,即数据的组织形式。 数据结构一般包括以下三方面内容:数据的逻辑结构、数据的存储结构、数据的运算 ①数据的逻辑结构是从逻辑关系上描述数据,与数据元素的存储结构无关,是独立于计算机的。 数据的逻辑结构分类:线性结构和非线性结构。 线性表是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。 ②数据元素及其关系在计算机内的存储方式,称为数据的存储结构(物理结构)。 数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。 ③数据的运算。最常用的检索、插入、删除、更新、排序等。 4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储 (1)顺序存储:通常借助程序设计语言的数组描述。 (2)链接存储:通常借助于程序语言的指针来描述。 (3)索引存储:索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。 (4)散列存储:该方法的基本思想是:根据元素的关键字直接计算出该元素的存储地址。 5.算法必须满足5个准则:输入,0个或多个数据作为输入;输出,产生一个或多个输出;有穷性,算法执行有限步后结束;确定性,每一条指令的含义都明确;可行性,算法是可行的。 算法与程序的区别:程序必须依赖于计算机程序语言,而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类:类Pascal和类C。 6.评价算法的优劣:算法的"正确性"是首先要考虑的。此外,主要考虑如下三点: ①执行算法所耗费的时间,即时间复杂性; ②执行算法所耗费的存储空间,主要是辅助空间,即空间复杂性; ③算法应易于理解、易于编程,易于调试等,即可读性和可操作性。

2021年自考02331数据结构重点总结最终修订

自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出:算法+数据构造=程序。算法是对数据运算描述,而数据构造涉及逻辑构造和存储构造。由此可见,程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法,而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成,数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系,即数据组织形式。 数据构造普通涉及如下三方面内容:数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据,与数据元素存储构造无关,是独立于计算机。 数据逻辑构造分类:线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式,称为数据存储构造(物理构造)。 数据存储构造是逻辑构造用计算机语言实现,它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法:顺序存储、链接存储、索引存储、散列存储 (1)顺序存储:普通借助程序设计语言数组描述。 (2)链接存储:普通借助于程序语言指针来描述。 (3)索引存储:索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 (4)散列存储:该办法基本思想是:依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则:输入,0个或各种数据作为输入;输出,产生一种或各种输出;有穷性,算法执行有限步后结束;拟定性,每一条指令含义都明确;可行性,算法是可行。 算法与程序区别:程序必要依赖于计算机程序语言,而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类:类Pascal和类C。 6.评价算法优劣:算法"对的性"是一方面要考虑。此外,重要考虑如下三点: ①执行算法所耗费时间,即时间复杂性; ②执行算法所耗费存储空间,重要是辅助空间,即空间复杂性; ③算法应易于理解、易于编程,易于调试等,即可读性和可操作性。

自考数据结构公式汇总

自考数据结构公式汇总 1.O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、 O(n3)、O(n k)、O(2n)。 2.在顺序表中第i个位置插入一个结点的移动次数为n-i+1,插入平均移动n/2次,删 除顺序表第i个结点移动次数为n-i,平均移动(n-1)/2次。 3.定义变量p=(LinkList)malloc(sizeof(ListNode))或 p=(LinkNode*)malloc(sizeof(ListNode)) 4.单循环链表判断空:head= =head->next 5.共享向量空间判断满top1=top2-1 6.入队EnQueue,出队DeQueue,front=rear空队列,循环队列克服假上溢 7.循环队列判断队满(rear+1)%m=front,循环队列指针移动方向顺时针。判队列长度 (rear-front+m)%m 8.链队列判空:Q->front=Q->rear=NULL 9.求串长strlen,串复制strcpy(to,from),联接strcat(to,from),串比较strcmp(s1 大就大于s1小就小于,小写字母>大写字母),字符定位strchr 10.串的子串定位(模式匹配)下标从0开始,最坏情况下时间复杂度比较次数 O((n-m+1)m) 11.二维数组下标为0公式:行优先LOC(a00)+[i*n+j]*d,列优先LOC(a00)+[j*m+i]*d 12.三维数组下标为0公式:三维数组A mnp按行优先LOC(a ijk)=LOC(a000)+[i*n*p+j*p+k]*d 13.对称矩阵一共有n(n+1)/2个元素,存储位置 k=I*(I+1)/2+J(I=max(i,j),J=min(i,j))下标0开始 14.上三角矩阵:k=i*(2n-i+1)+j-i,下三角矩阵:k=i*(i+1)/2+j。上三角i>j下三角 i(k-1)/2,则元素a ij=0 16.三元组表组成:i(行)j(列)v(值),转置时间复杂度O(m*n),带行表的三元组表是一 种顺序存储结构。

自考数据结构 试题及答案解析

2015年lO月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共8页。满分l00分。考试时间l50分钟。 考生答题注意事项: 1.本卷所有试题必须在答题卡上作答。答在试卷上无效,试卷空白处和背面均可作草稿纸. 2.第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3.第二部分为非选择题。必须注明大、小题号,使用0.5毫米黑色字迹签字笔作答。 4.合理安排答题空间.超出答题区域无效。 第一部分选择题 一、单项选择题(本大题共l5小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题卡” 的相应代码涂黑。未涂、错涂或多涂均无分。

1.下列选项中,不属于线性结构的是 A.网 B.栈 C.队列 D.线性表 2.长度为n的顺序表,删除位置i上的元素(0≤i≤n一1),需要移动的元素个数为 A.n—i B.n—i—l C.i D.i+1 3.栈采用不同的存储方式时,下列关于出栈过程的叙述中,正确的是 A.顺序栈需要判定栈空,链栈也需要判定 B.顺序栈需要判定栈空,而链栈不需要判定 C.顺序栈不需要判定栈空,而链栈需要判定 D.顺序栈不需要判定栈空,链栈也不需要判定 4.若一个栈以数组V[0..n-1]存储,初始栈顶指针top为n,则x入栈的正确操作是 A.top=top+1;V[top]=x B.V[top]=x;top=top+1 C.top=top一1;V[mp]=x D.V[top]=x;top=top—l 5.在二维数组a[9][10]中:每个数组元素占用3个存储空间,从首地址SA开始按行优先

2018自考《数据库系统原理》填空题总结

第一章节数据库系统基本概念 1.文件系统中的数据独立性是指(设备)独立性。 2.在数据库方式下的信息处理中,(数据)占据了中心位置。 3.DBMS是位于(用户)和(OS)之间的一层数据管理软件。 4.数据模型不仅描述数据本身的特点,还要描述(数据之间的联系)。 5.DBS中,用户的数据和磁盘中的数据之间转换由(DBMS)实现。 6.在层次、网状模型中,用(指针)导航数据;而在关系模型中,用(关键码)导航数据。7.数据库的三级模式结构是对(数据)的三个抽象级别。 8.DBS中存放三级结构定义的DB称为(数据字典)。 9.DBS的全局结构体现了其(模块功能)结构。 10.DBMS为应用程序运行时开辟的DB系统缓冲区,主要用于(数据传输)和(模式转换)。11.层次模型用(树)型结构来表示实体间的联系。 12.在数据的人工管理阶段,程序与数据是(一一对应)的关系。 13.定义数据库的安全性和完整性的工作由(DBA)完成。 14.数据独立性的好处是(数据存储方式的变化不会影响到应用程序的使用)。 15.数据库的三级体系结构使用户能抽象地使用数据,不必关心(数据在计算机中的表示和存储) 。 16.概念设计阶段用到实体、实体集、属性和实体标识符等4个术语;逻辑设计阶段用到字段、记录、文件和关键码等4个术语; 第二章节数据库设计和ER模型 1.ER数据模型一般在数据(概念设计)阶段使用。 2.“为哪些表,在哪些字段上,建立什么样的索引”这一设计内容应该属于数据库设计中的(物理设计)阶段。 3.数据模型是用来描述数据库的结构和语义的,数据模型有(概念数据模型)和(结构数据模型)两类,ER模型是(概念数据模型)。 4.数据实施阶段包括两项重要的工作,一项是数据(载入),另一项是应用程序的编码和调试。5.ER图向关系模型转化要解决的问题是如何将实体和实体之间的联系转换成关系模式,如何确定这些关系模式的(属性和键)。 6.数据库的物理设计是对一个给定的(基本数据)模型选取一个最合适应用环境的物理结构的过程。 7.数据库设计中,将(各局部ER之间的联系)分ER图集成时,主要任务是增补。 8.数据库应用系统设计中逻辑设计的主要内容是把ER模型的(实体和联系)转换为关系模式。 9.ER方法是(概念数据模型)设计的方法。 10.现实世界到机器世界过渡的中间层次是(概念模型)。 11.概念设计的目标是(企业组织信息需求)产生反映的数据库概念结构,即概念模式。12.在DBD中,子类具有一个重要的性质:(继承性)。 13.DBD的逻辑设计分成两大部分:(DB逻辑结构设计和应用程序设计)。 14.关系模型用(关键码)表示实体之间的联系。 15.DBS的维护工作由(DBA) 承担。 16.概念设计是设计能够反映用户需求的数据库概念结构,即概念模型。 17.ER模型是人们认识客观世界的一种方法、工具。 18.ER模型具有客观性和主观性两重含义。 第三章节关系模式设计理论

全国2014年4月自考数据结构真题

绝密★考试结束前 全国2014年4月高等教育自学考试 数据结构试题 课程代码:02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项: 1.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸” 的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关 ..的概念是 A.栈 B.链表 C.顺序表 D.二叉链表 2.顺序表中有10个数据元素,若第一个元素的存储地址是1000,则最后一个元素地址是1036,第5个元素的地址是 A.1010 B.1016 C.1018 D.1019 3.设栈的初始状态为空,元素1、2、3、4、5、6依次入栈,得到的出栈序列是(2,4,3,6,5,1),则栈的容量至少是 A.2 B.3 C.4 D..6 4.下列关于队列的叙述中,错误 ..的是 A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 1

D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 B.节省存储空间 C.便于输入输出 D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14 B.64 C.127 D.128 7.下列选项为完全二叉树的是 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e B. e C. 2e D. n+e 9.无向图中所有顶点的度数之和与所有边数之比是 A.1/2 B.1 C.2 D.4 10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 11.对序列(15,9,7,8,20,-1,4)进行排序,若一趟排序后的结果为(-1,15,9,7,8,20,4),则采用的排序方法是 A.归并排序 B.快速排序 C.直接选择排序 D.冒泡排序 12.比较次数与待排序列初始状态无关的排序方法是 A.快速排序 B.冒泡排序 C.直接插入排序 D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找 B.二分查找 C.顺序查找 D.折半查找 14.下列关于m阶B树的叙述中,错误 ..的是 2

自考02142《数据结构导论》串讲笔记

: 第一张概论 引言 两项基本任务:数据表示,数据处理 软件系统生存期:软件计划,需求分析,软件设计,软件编码,软件测试,软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型,这种数学模型的建立,选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据,逻辑结构和运算 数据:凡是能够被计算机存储,加工的对象通称为数据 数据元素:是数据的基本单位,在程序中作为一个整体加以考虑和处理。又称元素,顶点,结点,记录。 数据项:数据项组成数据元素,但通常不具有完整确定的实际意义,或不被当做一个整体对待。又称字段或域,是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系:是指数据元素之间的关联方式,又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构: 1 集合:任何两个结点间没有逻辑关系,组织形式松散 2 线性结构:结点按逻辑关系依次排列成一条“锁链” 3 树形结构:具有分支,层次特性,形态像自然界中的树 { 4. 图状结构:各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式,内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算:运算是指在任何逻辑结构上施加的操作,即对逻辑结构的加工。 。 加工型运算:改变了原逻辑结构的“值”,如结点个数,结点内容等。 引用型运算:不改变原逻辑结构个数和值,只从中提取某些信息作为运算的结果。 引用:查找,读取 加工:插入,删除,更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B,而B的实现不需要利用A,则称A可以归约为B。

自考02142《大数据结构导论》串讲笔记

第一概论 1.1 引言 两项基本任务:数据表示,数据处理 软件系统生存期:软件计划,需求分析,软件设计,软件编码,软件测试,软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型,这种数学模型的建立,选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据,逻辑结构和运算 数据:凡是能够被计算机存储,加工的对象通称为数据 数据元素:是数据的基本单位,在程序中作为一个整体加以考虑和处理。又称元素,顶点,结点,记录。 数据项:数据项组成数据元素,但通常不具有完整确定的实际意义,或不被当做一个整体对待。又称字段或域,是数据不可分割的最小标示单位。 1.2.2 数据的逻辑结构 逻辑关系:是指数据元素之间的关联方式,又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构: 1 集合:任何两个结点间没有逻辑关系,组织形式松散 2 线性结构:结点按逻辑关系依次排列成一条“锁链” 3 树形结构:具有分支,层次特性,形态像自然界中的树 4. 图状结构:各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式,容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算:运算是指在任何逻辑结构上施加的操作,即对逻辑结构的加工。 加工型运算:改变了原逻辑结构的“值”,如结点个数,结点容等。 引用型运算:不改变原逻辑结构个数和值,只从中提取某些信息作为运算的结果。 引用:查找,读取 加工:插入,删除,更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B,而B的实现不需要利用A,则称A可以归约为B。 假如X是S上的一些运算的集合,Y是X的一个子集,使得X中每一运算都可以规约为Y中的一个或多个运算,而Y中任何运算不可规约为别的运算,则称Y中运算(相对于X)为基本运算。 将逻辑结构S和在S上的基本运算集X的整体(S,X)称为一个数据结构。数据结构包括逻辑结构和处理方式。

全国自学考试数据结构导论试题及答案(4套)

全国2011年1月自学考试数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在顺序表中查找第i个元素,时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n) 2.树形结构中,度为0的结点称为( ) A.树根 B.叶子 C.路径 D.二叉树 3.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={,,,},则图G的拓扑序列是 ( ) A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7 4.有关图中路径的定义,表述正确的是( ) A.路径是顶点和相邻顶点偶对构成的边所形成的序列 B.路径是不同顶点所形成的序列 C.路径是不同边所形成的序列 D.路径是不同顶点和不同边所形成的集合 5.串的长度是指( ) A.串中所含不同字母的个数 B.串中所含字符的个数 C.串中所含不同字符的个数 D.串中所含非空格字符的个数 6.组成数据的基本单位是( ) A.数据项 B.数据类型 C.数据元素 D.数据变量 7.程序段 i=n;x=0; do{x=x+5*i;i--;}while (i>0); 的时间复杂度为( ) A.O(1) B.O(n) C.O(n2) D.O(n3) 8.与串的逻辑结构不同的 ...数据结构是( ) A.线性表 B.栈 C.队列 D.树

自考数据库系统原理完整版

自考《数据库系统原理》串讲笔记 第一章数据库基础知识 学习目的与要求: 本章属于基础知识,主要是对一些概念的理解和记忆。没有难点,相对的重点是数据模型的四个层次,数据库管理系统的功能,数据库系统的全局结构。 考核知识点与考核要求 1.1数据管理技术的发展阶段(识记) 1.2数据描述的术语(领会) 1.3数据抽象的级别(领会) 1.4数据库管理系统(DBMS) (领会) 1.5数据库系统(DBS)(领会) 1.1 数据管理技术的发展 几个数据库的基本术语: 数据:描述事物的符号记录 数据处理:是指从某些已知的数据出发,推导加工出一些新的数据,这些新的数据又表示了新的信息。 数据管理:是指数据的收集、整理、组织、存储、维护、检索、传送等操作,这部分操作是数据处理业务的基本环节,而且是任何数据处理业务中必不可少的共有部分。 数据管理技术:对数据的收集、整理、组织、存储、维护、检索、传送等操作,基本目的就是从大量的,杂乱无章的,难以理解的数据中筛选出有意义的数据。 数据处理是与数据管理相联系的,数据管理技术的优劣,将直接影响数据处理的效率。 1.人工管理阶段(20世纪50年代中期以前) 1)数据不保存在机器中; 2)没有专用软件对数据进行管理; 3)只有程序的概念,没有文件的概念; 4)数据面向程序。 2. 文件系统阶段特点与缺陷(20世纪50年代后期至60年代中期) 1)数据可长期保存在磁盘上; 2)数据的逻辑结构与物理结构有了区别; 3)文件组织呈现多样化; 4)数据不再属于某个特定程序,可以重复使用; 5)对数据的操作以记录为单位。 文件系统三个缺陷: 1)数据冗余性 2)数据不一致性

自考《数据结构》真题和答案

2016年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共7页,满分100分,考试时间150分钟。 考生答题注意事项: 1 ?本卷所有试题必须在答题卡上作答。答在试卷上无效,试卷空白处和背面均可作草稿纸 2. 第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑' 3. 第二部分为非选择题。毖须注明大、小题号,使用0. 5毫米黑色字迹签字笔作答。 4 ?合理安排答题空间,超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共15小题,每小题2分,共30分> 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1. 下列选项中,不属于线性结构特征的是 A.数据元素之间存在线性关系 B .结构中只有一个幵始结点 C.结构中只有一个终端结点 D .每个结点都仅有一个直接前趋

2. 设17个元素的顺序表中,若将第个元素e 移动到第个位置,

不改变除e外其他元素之间的相对次序,则需移动的表中元素个数是 A. AM B, i-i C.上汁】D讨3 .若用一个大小为7的数组作为循环队列的存储结构,且当前rew和盘Ont的值分别 为2和4,在此之前的操作是从队列中删除了一个元素及加入两个元素,请问这3 个操作之前rear和矗Ont的值分别是 A. 0 和I B . 0 和3 C . 3 和6 D . 4 和5 4 .已知广义表LS=(((a)) , ((b , (c)) , (d , (e , f))) , 0) , LS 的长度是 A. 2 B . 3 C . 4 D. 5 5.—棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点 于中包含的结点数是 A. k B. 2k-1 C k2 D .2k-1 6.如果某二叉树的前序遍历序列为abced,中序遍历序列为cebda,则该二叉树的后序遍历序列是 A. cedba B decba C ecdba D . ecbad 7.—个森林有m棵树,顶点总数为n,则森林中含有的总边数是 A. m B. n-l C n-m n+m 8.设图的邻接矩阵A如下所示。各顶点的度依次是

2020年10月全国自考数据结构试题及答案解析.doc

??????????????????????精品自学考料推荐?????????????????? 全国 2018 年 10 月高等教育自学考试 数据结构试题 课程代码: 02331 一、单项选择题(本大题共15 小题,每小题 2 分,共 30 分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选 均无分。 1.数据结构是() A.一种数据类型 B.数据的存储结构 C.一组性质相同的数据元素的集合 D.相互之间存在一种或多种特定关系的数据元素的集合 2.算法分析的目的是() A.辨别数据结构的合理性 B.评价算法的效率 C.研究算法中输入与输出的关系 D.鉴别算法的可读性 3.在线性表的下列运算中,不.改变数据元素之间结构关系的运算是() A .插入 B .删除 C.排序 D .定位 4.若进栈序列为 1, 2, 3,4, 5, 6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为() A . 3,2, 6, 1, 4, 5 B .3, 4, 2,1, 6, 5 C. 1, 2, 5, 3,4, 6 D .5, 6, 4, 2, 3,1 5.设串 sl=″ Data Structures with Java ″ ,s2=″it ″,则子串定位函数index(s1,s2)的值为 ()A . 15 B .16 C. 17 D .18 6.二维数组 A[8][9] 按行优先顺序存储,若数组元素A[2][3] 的存储地址为 1087,A[4][7] 的存储地址为1153,则数组元素 A[6][7] 的存储地址为() A . 1207 B .1209 1

6月数据结构自考试题及答案

全国2006年10月高等教育自学考试 数据结构试卷 课程代码:02331 一、单项选择题<本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据结构是<) A.一种数据类型 B.数据的存储结构 C.一组性质相同的数据元素的集合 D.相互之间存在一种或多种特定关系的数据元素的集合 2.算法分析的目的是<) A.辨别数据结构的合理性 B.评价算法的效率 C.研究算法中输入与输出的关系 D.鉴别算法的可读性 3.在线性表的下列运算中,不.改变数据元素之间结构关系的运算是<) A.插入B.删除 C.排序D.定位 4.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为<)A.3,2,6,1,4,5 B.3,4,2,1,6,5 C.1,2,5,3,4,6 D.5,6,4,2,3,1 5.设串sl=″Data Structures with Java″,s2=″it″,则子串定位函数index(s1,s2>的值为 <)A.15 B.16 C.17 D.18 6.二维数组A[8][9]按行优先顺序存储,若数组元素A[2][3]的存储地址为1087,A[4][7]的存储地址为1153,则数组元素A[6][7]的存储地址为<) A.1207 B.1209 C.1211 D.1213 7.在按层次遍历二叉树的算法中,需要借助的辅助数据结构是<) A.队列B.栈 C.线性表D.有序表 8.在任意一棵二叉树的前序序列和后序序列中,各叶子之间的相对次序关系<) A.不一定相同B.都相同

2008年1月全国自考试题数据结构试卷

1 全国2008年1月高等教育自学考试 数据结构试题 课程代码:02331 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.逻辑上通常可以将数据结构分为( ) A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线性结构 D.初等结构和组合结构 2.在下列对顺序表进行的操作中,算法时间复杂度为O(1)的是( ) A.访问第i 个元素的前驱(1next= =NULL C.head!=NULL D.head –>next= =head 4.已知栈的最大容量为4。若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为( ) A.5,4,3,2,1,6 B.2,3,5,6,1,4 C.3,2,5,4,1,6 D.1,4,6,5,2,3 5.与线性表相比,串的插入和删除操作的特点是( ) A.通常以串整体作为操作对象 B.需要更多的辅助空间 C.算法的时间复杂度较高 D.涉及移动的元素更多 6.假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是(注:矩阵的行列下标均从1开始)( ) A.?????? ? ? ?--004050000000007 06080 B.?????? ? ? ?--000000040530007 060 8

自考数据结构重点知识

第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位,可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义: ·逻辑结构:从逻辑结构上描述数据,独立于计算机。 ·线性结构:一对一关系。 ·线性结构:多对多关系。 ·存储结构:是逻辑结构用计算机语言的实现。 ·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·索引存储结构:·稠密索引:每个结点都有索引项。 ·稀疏索引:每组结点都有索引项。 ·散列存储结构:如散列表。 ·数据运算。·对数据的操作。定义在逻辑结构上,每种逻辑结构都有一个运算集合。 ·常用的有:检索、插入、删除、更新、排序。 数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。 ·原子类型:由语言提供。 ·结构类型:由用户借助于描述机制定义,是导出类型。 抽象数据类型ADT:·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构,设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程,以一个或多个值输入,并以一个或多个值输出。 评价算法的好坏的因素:·算法是正确的; ·执行算法的时间; ·执行算法的存储空间(主要是辅助存储空间); ·算法易于理解、编码、调试。 时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模n的函数。

渐近时间复杂度:是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。 评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。 空间复杂度:是某个算法的空间耗费,它是该算法所求解问题规模n的函数。 算法的时间复杂度和空间复杂度合称算法复杂度。 第二章线性表 线性表是由n≥0个数据元素组成的有限序列。n=0是空表;非空表,只能有一个开始结点,有且只能有一个终端结点。 线性表上定义的基本运算: ·构造空表:Initlist(L) ·求表长:Listlength(L) ·取结点:GetNode(L,i) ·查找:LocateNode(L,x) ·插入:InsertList(L,x,i) ·删除:Delete(L,i) 顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。地址计算:LOCa(i)=LOCa(1)+(i-1)*d;(首地址为1) 在顺序表中实现的基本运算: ·插入:平均移动结点次数为n/2;平均时间复杂度均为O(n)。 ·删除:平均移动结点次数为(n-1)/2;平均时间复杂度均为O(n)。 线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同,为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还存储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。 单链表运算:·建立单链表·头插法:s->next=head;head=s;生成的顺序与输入顺序相反。平均时间复杂度均为O(n)。 ·尾插法:head=rear=null;if(head=null) head=s;else r->next=s;r=s;平均时间复杂度均为O(n)

高等教育自学考试--数据结构试题

一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在数据结构中,数据的逻辑结构可以分成() A.内部结构和外部结构 B.线性结构和非线性结构 C.紧凑结构和非紧揍结构 D.动态结构和静态结构 2.在以单链表为存储结构的线性表中,数据元素之间的逻辑关系用() A.数据元素的相邻地址表示 B.数据元素在表中的序号表示 C.指向后继元素的指针表示 D.数据元素的值表示 3.设p指向单链表中的一个结点,s指向待插入的结点,则下述程序段的功能是() s -> next = p -> next; p -> next = s; t = p -> data; p -> data = s -> data; s ->data = t; A.结点*p与结点*s的数据域互换 B.在p所指结点的元素之前插入元素 C.在p所指结点的元素之后插入元素 D.在结点*p之前插入结点*s 4.栈和队列都是() A.限制存取位置的线性结构 B.顺序存储的线性结构 C.链式存储的线性结构 D.限制存取位置的非线性结构 5.若数组s[0..n-1]为两个栈s1和s2的共用存储空间,且仅当s[0..n-1]全满时,各栈才不能进行进

栈操作,则为这两个栈分配空间的最佳方案是:s1和s2的栈顶指针的初值分别为()A.1和n+1 B.1和n/2 C.-1和n D.-1和n+1 6.执行下列程序段后,串X的值为() S=??abcdefgh??; T=??xyzw??; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y); A.??cdefgh?? B.??cdxyzw?? C.??cdefxy?? D.??cdefef?? 7.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为() A.数组的元素处在行和列两个关系中 B.数组的元素必须从左到右顺序排列 C.数组的元素之间存在次序关系 D.数组是多维结构,内存是一维结构 8.从广义表LS=((p, q), r, s)中分解出原子q的运算是() A.tail (head (LS)) B.head (tail (head (LS))) C.head (tail (LS)) D.tail (tail (head (LS))) 9.在具有n个叶子结点的严格二叉树中,结点总数为() A.2n+1 B.2n C.2n-1 D.2n-2 10.若是有向图的一条边,则称() A.v i邻接于v j B.v j邻接于v i C.v i和v j相互邻接 D.v i与v j不相邻接

相关文档
相关文档 最新文档