数据结构与算法作业
《数据结构与算法》作业
说明：
1、题号形式: 每题都以【sn，cha，sec】开头，sn表明本题的题目序号，每道题都有唯一的序号；cha表示内容所在的章；sec表示内容所在的节。如【17，2，1】表示序号17的题来自第2章第1节。
2、题型：1) 选择题：序号1-180题
2) 是非题：序号181-220题
3) 分析计算作图题：序号221-250题（选自《数据结构题集》—严蔚敏等编）
3、内容取舍：根据本学期上课课件中的内容，未上课章节的练习可舍弃。
4、必做题或选做题：是非题和选择题（序号1-220）只要在上过课的章节中都是必做题，分析计算作图题（序号221-250）在每题后标出是必做题还是选做题，其中16个必做题14个选做题。
1) 选择题：序号1-180题
【1，1，1】数据结构形式地定义为（D，S），其中D是①B 的有限集合，S 是D上的②D 的有限集合。
① A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作
② A. 结构 B. 操作 C. 存储 D. 关系
【2，1，1】数据结构中，从逻辑上可以把数据结构分成① D 。
① A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构
C. 内部结构和外部结构
D. 线性结构和非线性结构
【3，1，1】数据结构是研究数据的①C 以及它们之间的相互关系。
① A. 理想结构，物理结构 B. 理想结构，抽象结构
（C）物理结构，逻辑结构（D）抽象结构，逻辑结构
【4，1，1】数据的定义取决于数据的逻辑结构，而数据的实现取决于数据的物理结构。
A. 正确A
B. 不正确
【5，1，2】在数据结构中，与所使用的计算机无关的是数据的①C 结构。
① A.存储 B.物理 C.逻辑 D.物理与存储
【6，1，3】数据结构课程主要研究以下三方面的内容，它们是①D 。
① A. 数据、数据元素、数据类型
1
B. 数据元素、数据类型、算法实现
C. 数据元素、数据的逻辑结构、数据的存储结构
D. 数据的逻辑结构、数据的存储结构、数据的运算
【7，1，3】在下列叙述中，正确的是①C 。
① A. 数据的逻辑结构要考虑数据元素本身的内容
B. 不同类型的数据元素可以归类到同一的逻辑结构中
C. 数据元素之间的关联关系在数据的逻辑结构中体现
D. 数据元素是数据不可分割的最小标识单位
【8，1，4】下面程序段的时间复杂度是①D 。
s=0;
for(i=o; i for(j=0; j s = s + a[i][j]; ① A. O(1) B. O(m+n) C. O(logmn) D. O(m*n) 【9，1，4】在以下的复杂度量级中，量级最低的是①B 。 ① A. O(n) B. O(log2n) C. O(nlog2n) D. O(n2) 【10，1，4】计算机算法是指①D 。 ① A.计算方法 B.排序方法 C.调度方法 D.解决问题的有限运算序列 【11，1，4】计算机算法必须具备输入、输出和①B 等五个特性。 ① A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、稳定性和有穷性 D.易读性、稳定性和安全性 【12，1，4】设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（D） A．O（log2n）B．O(n) C．O(nlog2n) D．O(n2) 【13，1，4】算法分析的两个主要方面是（ C ）。 A．数据复杂性和程序复杂性 B. 可读性和文档性 C. 时间复杂度和空间复杂度 D. 正确性和简单性 【14，1，4】算法分析的目的是（C）。 2 A．找出数据结构的合理性B．研究算法中的输入/输出关系 C．分析算法的效率以求改进D．分析算法的易读性 【15，1，4】设n>=10，下面程序段的时间复杂度是①D 。 for(i=10; i j=k=0; while(j+k<=i) if(j>k)k++; else j++; } A．O（log2n）B．O(n) C．O(nlog2n) D．O(n2) 【16，2，0】在下列存储结构中，具备随机存取特性的是(A) A. 顺序表 B. 单链表 C. 单循环链表 D. 带头结点的双循环链表 【17，2，1】线性表是①A . ① A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 【18，2，1】下列有关线性表的叙述中，正确的是①A 。 ① A. 线性表中的元素之间是线性关系 B. 线性表中至少有一个元素 C. 线性表中的任一元素有且仅有一个直接前趋 D. 线性表中的任一元素有且仅有一个直接后继 【19，2，1】链表与顺序表相比，在链表上作插入、删除运算要方便些。 A. 正确A B. 不正确 【20，2，2】下述哪一条是顺序存储结构的优点？ A ① A.存储密度大 B.插入方便 C.删除方便 D.可方便地用于各种逻辑结构的存储表示 【21，2，2】关于一维数组和线性表，下列说法正确的是① A 。 ① A. 前者长度固定，后者长度可变 B. 后者长度固定，前者长度可变 C. 两者长度都固定 D. 两者长度都可变 【22，2，2】在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动① D 个元素。 ① A. 1 B. n-i C. n-i-1 D.n-i+1 3 【23，2，2】如果某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，那么采用① A 存储方式最节省时间。 ① A. 顺序表 B. 单链表 C. 双链表 D. 循环链表 【24，2，2】对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的① A 个元素。 ①(A) n/2 (B) (n+1)/2 (C) (n -1)/2 (D) n 【25，2，2】顺序表的特点是①B 。 ① A. 逻辑上相邻的结点其物理位置不相邻 B. 逻辑上相邻的结点其物理位置亦相邻 C. 顺序表不是随机存储结构 D. 在顺序表中插入和删除操作比在链表上方便 【26，2，2】向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（C ）个元素。 A. 115 B. 114 C. 58 D. 57 【27，2，2】下述哪一条是顺序存储结构的缺点？ C A.存储密度太大 B.随机存取 C.一般要估计最大的需要空间 D.只能应用于少数几种逻辑结构的存储表示 【28，2，3】在单链表中，增加头结点的目的是①C 。 ① A.使单链表至少有一个结点 B.标志表中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储表示 【29，2，3】线性表按链式方式存储时，每个结点的存储包括① B 两部分。 ① A.数据值与符号 B.数据与指针 C.数据与表名 D.数据项与符号 【30，2，3】链表对于数据元素的插入与删除是①B 。 ① A. 不需移动结点，不需改变结点指针 B. 不需移动结点，只需改变结点指针 C. 只需移动结点，不需改变结点指针 D. 既需移动结点，又需改变结点指针 【31，2，3】若要求能快速地实现在链表的末尾插入和删除结点的运算，则选择①B 最合适。 ① A. 单链表 B. 带尾指针的单循环链表 4 C. 双链表 D. 双循环链表 【32，2，3】在一个单链表中，已知q所指结点是p所指结点的前驱结点，若要在q 和p所指结点之间插入s所指的结点，则执行①B 。 ① A. s->next = p->next; p->next = s; B. q->next = s; s->next = p; C. p->next = s; s->next = q; D. p->next = s->next; s->next = p; 【33，2，3】带头结点的单链表Head为空表的判定条件是( B ) 。 A. Head->next==Head B. Head->next==NULL C. Head!=NULL D. Head==NULL 【34，2，3】在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是①A 。 ① A. O(n) B. O(log2n) C. O(1) D. O(n2) 【35，2，3】链表不具有的特点是① A 。 ① A. 可随机访问任一元素 B. 插入和删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间和线性表长度成正比 【36，2，3】线性表采用链式存储时，其地址① C 。 ① A. 必须是连续的 B. 必须是不连续的 C. 连续与否均可 D. 部分地址必须是连续的 【37，2，3】给定有n个元素的向量，建立一个有序单链表的时间复杂度是① D 。 ① A. O(n) B. O(log2n) C. O(nlog2n) D. O(n2) 【38，2，3】循环链表的主要优点是①D 。 ①A．不再需要头指针了 B．已知某个结点的位置后，能够容易找到他的直接前趋 C．在进行插入、删除运算时，能更好的保证链表不断开 D．从表中的任意结点出发都能扫描到整个链表 【39，2，3】在单链表中，指针p指着结点A,若要删除A之后的结点（若存在），则执行①B 。 ① A. p = p->next; B. p->next = p->next->next; C. p = p->next->next; 5 D. p->next = p; 【40，2，3】在长度为n 的双链表中某结点（已知其地址）之前，插入一个新结点的时间复杂度是①C 。 ① A. O(n) B. O(log2n) C. O(1) D. O(n2) 【41，2，3】链表只能用指针和动态变量来实现。 ① A. 正确 B. 不正确 B 【42，2，3】将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为( A ) q=NULL; while (p!=NULL) { （） } p=q; A．r=q; q=p; p=p -> next; q -> next=r; B．q=p; r=q; p=p -> next; q -> next=r; C．r=q; p=p -> next; q=p; q -> next=r; D．q=p; p=p -> next; r=q; q -> next=r; 【43，3，1】若一个栈的输入序列是1,2,3,……,n,输出序列的第一个元素是n,则第i个输出元素是①D 。 ① A. n-i B. n-i+1 C. i D. 不确定 【44，3，1】链栈与顺序栈相比，有一个比较明显的优点是① B 。 ① A. 插入操作更加方便 B. 通常不会出现栈满的情况 C. 不会出现栈满的情况 D. 删除操作更加方便 【45，3，1】一个栈的入栈序列是a,b,c,d, 则下列序列中不可能的输出序列是① D 。 ① A. acbd B. dcba C. acdb D. dbac 【46，3，1】栈的特点是①B 。 ①A、先进先出B、后进先出C、进优于出D、出优于进 6 【47，3，1】栈和队列都是①C 。 ①A、顺序存储的线性结构B、链式存储的线性结构 C、操作受限的线性结构 D、操作受限的非线性结构 【48，3，1】设有一空栈，现有输入序列为1,2,3,4,5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列为C 。 A、5,4,3,2,1 B、2,1 C、2,3 D、2,4 【49，3，1】作进栈操作时，应先判断栈是否为① B 。 ①A、空B、满C、上溢D、下溢 【50，3，1】一个栈的进栈序列是a,b,c,d,e, 则栈的不可能的出栈序列是①B 。 ① A. edcba B. dceab C. decba D. abcde 【51，3，1】若某堆栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为n，则第i个输出元素为（ A ）。 A.n-i+l B．n-i C．i D．哪个元素无所谓 【52，3，1】下面哪种数据结构不适合作栈的存储结构基础（D）。 A．数组 B. 单链表 C. 静态链表 D. 二叉树结构 【53，3，1】栈结构通常采用的两种存储结构是（D）。 A. 线性存储结构和链表存储结构 B. 散列方式和索引方式 C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 【54，3，1】若某堆栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为k（1<=k<=n），则第i个（i>1）输出元素应符合条件（ C ）。 A. 大于k的数B．大于i的数C．[k-i+1,k+i-1]之间的数D．哪个元素无所谓 【55，3，1】栈是一种线性结构。 A. 正确A B. 不正确 【56，3，1】当字符序列x5y 作为字符堆栈的输入时，输出长度为3的且可以作为C 语言标识符的个数是（ A ）。 A. 3个B．4个C．5个D．6个 【57，3，2】设计一个判别表达式中左右括号是否配对出现的算法，最好采用① C 结构。 ① A. 线性表 B. 队列 C. 堆栈 D. 树 7 【58，3，2】采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的（C）进行。 A. 任意位置 B. 链表头尾两端 C. 链表头一端 D. 链表尾一端 【59，3，2】对一个线性表，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据之间的逻辑关系。则应该用（ C ）作为存储方式。 A. 顺序方式 B. 链接方式 C. 散列方式 D. 以上方式均可 【60，3，3】递归函数f(n)=f(n-1)十n(n>1)的递归出口，比较合理的是（ B ）。A．f(1)=0 B．f(1)=1 C．f(0)=0 D．f(n)=n 【61，3，4】队列的操作原则是① A 。 ① A.先进先出 B.先进后出 C.只能进行插入 D.只能进行删除 【62，3，4】判断一个循环队列是空队列的条件是① D 。 ① A. Q.rear == Q.front B. Q.front == 0 C. Q.rear == 0 D. (Q.rear+1)%maxsize == Q.front 【63，3，4】对于下图所示的循环队列，队满的条件是①D ；队空的条件是②A 。 ①、②、A、rear=front B、rear=front+1 C、ront=rear+1 D、front=(rear+1)%MAXSIZE 【64，3，4】在具有n个单元顺序存储的循环队列中，队满时共有① B 个元素。 ① A.n+1 B.n-1 C.n D.n+2 【65，4，1】串是一种特殊的线性表，其特殊性体现在① C 。 8 ① A.可以顺序存储 B.可以用链表存储 C.数据元素是一个字符 D.数据元素可以是多个字符 【66，4，1】设串s1 = "Hello",s2="Student"，函数Concat(x,y)返回x和y的连接串，Subs(s,i,j)返回串s的从序号i的字母开始的j个字符组成的子串，Length(s)返回串s的长度，则下面函数Length(Concat(Subs(s2,Length(s1),3),Subs(s2,3,Length(s1)))的结果串是① B 。 ① A. 7 B. 8 C. 9 D. entudent 【67，4，1】串是（ D ）。 A.少于一个字母的序列 B.任意个字母的序列 C.不少于一个字符的序列 D.有限个字符的序列 【68，4，1】串的长度是（ D ）。 A. 串中不同字母的个数 B. 串中不同字符的个数 C. 串中所含字符的个数，且大于0 D. 串中所含字符的个数 【69，4，1】如果两个串含有相同的字符集，则说两者相等。 A. 正确 B. 不正确B 【70，4，1】串中任意多个连续字符组成的子序列称为该串的子串。 A. 正确A B. 不正确 【71，4，2】若某串的长度小于一个常数，则采用 C 存储方式最为节省空间。A. 链式 B. 堆结构 C. 顺序 【72，4，3】设有两个串p和q，求q在p中首次出现的位置的运算是（ B ）。 A.连接 B.模式匹配 C.求子串 D.求串长 【73，4，3】字符串'ababaabab'的nextval为（ A ）。 A．（0，1，0，1，0，4，1，0，1） B.（0，1，0，1，0，2，1，0，1）C．（0，1，0，1，0，0，0，1，1） D.（0，1，0，1，0，1，0，1，1） 【74，4，3】字符串'ababaabab'的next[j]为（ D ）。 A．（0，1，1，2，3，4，1，3，2） B.（0，1，2，2，3，2，2，3，4）C．（0，1，1，2，1，2，2，3，2） D.（0，1，1，2，3，4，2，3，4）【75，4，3】用于模式匹配的字符串'abcdefa'的next[j]为（ D ）。 9 A．（0，1，1，1，2，2，2） B.（0，1，1，1，1，2，2） C．（1，1，1，1，1，1，2） D.（0，1，1，1，1，1，1） 【76，5，1】存取数组中任一元素的时间都是相等的，这种存取方式为① B 存取方式。 ① A. 顺序 B. 随机 C. 线性 D. 非线性 【77，5，1】二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从0到5，则存放M至少需要①C 个字节。 ①、 A. 54 B. 40 C. 324 D. 240 【78，5，1】数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j 从1到10，从首地址SA开始连续存放在存储器内，若该数组按行存放时，元素A[8][5]的起始地址是①C 。 ①、 A. SA+141 B. SA+144 C. SA+222 D. SA+225 【79，5，1】一个一维数组第一个元素的存储单元的地址是100，每个元素的长度是6，则它的第5个元素的地址是①D 。 ① A. 130 B. 105 C. 106 D. 124 【80，5，1】两维数组是一种非线性结构。 A. 正确 B. 不正确B 【81，5，2】二维数组M的每个元素占4个字符，行下标i的范围从0到8，列下标j 的范围从0到9，则存放M至少需要①D 个字节。 ① A. 90 B. 180 C. 320 D. 360 【82，5，2】二维数组M的每个元素占4个字符，行下标i的范围从0到8，列下标j 的范围从0到9，若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的① C 元素的起始地址一致。 ① A. M[8][5] B. M[5][8] C. M[4][9] D. M[5][9] 【83，5，2】若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ B ）。 A. 正确 B. 错误 【84，5，2】数组A三维的长度分别为b3,b2,b1；每个数组元素占一个存储单元；LOC[0，0，0]为基址。若以行序为主序，则A[i,j,k] = ( A ) (其中0<=i 10 11 0<=k A. LOC[0, 0, 0] + i*b2*b1 + j*b1 + k; B. LOC[0, 0, 0] + i*b3*b2 + j*b1 + k; C. LOC[0, 0, 0] + b3*i +b2*j +k; D. LOC[0, 0, 0] + b3*i*j +b2*j +k; 【85，5，3】设n 阶方阵是一个上三角矩阵，则需要存储的元素个数是 ① B 。 ① A. n 2/2 B. n(n+1)/2 C. n D. n 2 【86，5，3】一个n ×n 的对称矩阵，如果以行或列为主序存入内存，则其压缩存储的 容量为（ C ）。 A. n×n B. n×n/2 C. n×(n+1)/2 D. (n+1)×(n+1)/2 【87，5，3】下列矩阵是一个 ① D 。 ????? ? ??????70 00650004300021 ① A. 上三角矩阵 B. 三对角矩阵 C. 稀疏矩阵 D. 上述A 和B 正确 【88，5，3】将n 阶对称矩阵Anxn 的下三角部分按行序存放在一维数组 B[1…n(n+1)/2] 中，那么下三角部分中任一元素aij （i>=j ）,在一维数组中的下标k 的值是 B ① 。 ① A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 【89，5，3】对稀疏矩阵进行压缩存储的目的是便于计算。 ① A. 正确 B. 不正确B 【90，5，3】关于矩阵压缩存储，下面的说法中，不正确的是（ B ） A ．只须存放对称矩阵中包括主对角线元素在内的下(或上)三角部分的元素即可 B ．只须存放对称矩阵中的非零元素即可 C ．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储 D ．稀疏矩阵中大量值为零的元素分布没有规律，因此可以采用三元组表方法存储 【91，5，3】对一些特殊矩阵采用压缩存储的目的主要是为了（ D ） A ．表达变得简单 B ．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销 【92，5，3】若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了 （ C ）个数组元素。 A．n*n B．n*(n-1) C．n*(n+1)／2 D．n*(n-1)/2 【93，5，3】三元组表不包括(D ) A. 行数 B.列数 C. 元素值 D.元素总数 【94，5，3】设已知一个稀疏矩阵的三元组如下： (1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),则其转置矩阵的三元组表中第3个三元组为（ A ）。 A.（2,1,3） B.(3,1,5) C.(3,2,-1) D.(2,3,-1) 【95，5，3】若将n阶下三角矩阵的所有非零元素存放在一个一维数组B中，则该矩阵在B中占用了（ C ）个数组元素。 A．n*n B．n*(n-1) C．n*(n+1)／2 D．n*(n-1)/2 【96，6，1】树最适合用来表示① C 。 ① A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 【97，6，1】除根结点外，树上每个结点（B） A．可有任意多个孩子、任意多个双亲 B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲 【98，6，2】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为① A 。 ① A. 2h-1 B. 2(h-1) C. 2*h-1 D. 2*h 【99，6，2】下图所示的二叉树中，①C 不是完全二叉树。 12 【100，6，2】在一棵二叉树中，第5层上的结点数最多有①C 。 ① A. 10 B. 15 C. 16 D. 32 【101，6，2】在有n个结点的二叉链表中，值为空的链指针共有①A 。 ① A. n+1 B. n-1 C. n D. 2n 【102，6，2】具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（D）个指针域为空。 A．50 B．99 C．100 D．101 【103，6，2】设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是（C） A、6 B、5 C、4 D、3 【104，6，2】如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是①D 。 ① A. dbafec B. fecdba C. efcdba D. dbfeca 【105，6，3】n个结点深度为h的二叉树的线索化所需的时间复杂度是①C 。 ① A. O(1) B. O(hn) C. O(n) D. O(nlogh) 【106，6，3】在n个结点的二叉链表中，值为非空的指针域的个数是① D 。① A. 2n B. 2n+1 C. 2(n-1) D. n-1 【107，6，3】设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是① C 。 ① A. a是b祖先 B. a是b子孙 C.a在b左方 D. a在b右方 【108，6，3】二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法①B 。 ① A. 正确 B. 不正确 13 【109，6，3】在线索化二叉树中，T所指结点没有左子树的充要条件是①B 。 ① A. T->lchild == NULL B. T->ltag == 1 C. T->lchild == NULL && T->ltag == 1 D. 以上都不对 【110，6，3】关于二叉树的三种遍历，下列说法正确的是①D 。 ① A. 任意两种遍历序列都不可以唯一决定该二叉树 B. 任意两种遍历序列都可以唯一决定该二叉树 C. 先序遍历序列和后序遍历序列可以唯一决定该二叉树 D. 先序遍历序列和中序遍历序列可以唯一决定该二叉树 【111，6，3】任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序①A 。 ① A. 不发生变化 B. 发生变化 C. 不能确定 D. 以上都不对 【112，6，3】一棵左右子树均不空的二叉树在后序线索化后，其中空的右链域的个数是（B ） A. 不确定 B. 0 C. 1 D. 2 【113，6，3】如果一棵二叉树的先序序列和后序序列相反，则其高度一定等于其结点数。 ① A. 正确A B. 不正确 【114，6，3】在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列。 ① A. 正确 B. 不正确 B 【115，6，3】首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为(C) A.前序遍历 B.后序遍历 C.中序遍历 D.层次遍历 【116，6，3】已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（ D ）。 A．acbed B．decab C．deabc D．cedba 【117，6，3】某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是（ B ）的二叉树。 A.空或只有一个结点B．高度等于其结点数 C.任一结点无左孩子 D．任一结点无右孩子 14 【118，6，3】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为①C 。 ① A. 2h-1 B. 2(h-1) C. 2*h-1 D. 2*h 【119，6，3】由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。 A. 正确A B. 不正确 【120，6，3】前序遍历和中序遍历结果相同的二叉树为（ B ）。 A. 只有根结点的二叉树 B. 所有非叶子结点只有右子树的二叉树 C. 根结点无右孩子的二叉树 D. 根结点无左孩子的二叉树 【121，6，3】前序遍历和后序遍历结果相同的二叉树为（ A ）。 A. 只有根结点的二叉树 B. 所有非叶子结点只有右子树的二叉树 C. 根结点无右孩子的二叉树 D. 根结点无左孩子的二叉树 【122，6，3】树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中，① A 是正确的。 ① A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以上都不对 【123，6，4】若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（ C ）A. 根结点无右子树的二叉 B. 根结点无左子树的二叉树 C. 根结点可能有左二叉树和右二叉树 D. 各结点只有一个儿子的二叉树 【124，6，6】由分别带权为9,2,5,7的四个叶子结点构造一棵Huffman树，则该树的带权路径长度WPL为① C 。 ① A. 23 B. 37 C. 44 D. 46 【125，6，6】有m个叶子结点的Huffman树所具有的结点总数为① B 。 ① A. m+1 B. 2m-1 C. 2m D. 2m+1 【126，6，6】在有n 个叶子结点的哈夫曼树中结点总数为（ B ）。 A. 不确定 B. 2n-1 C. 2n D. 2n+1 【127，6，6】用HUFFMAN 算法求最优二叉树时，权越大的叶子离根越远。 15 A. 正确 B. 不正确B 【128，7，1】在一个无向图中，所有顶点的度数之和等于所有边数的① C 倍。 ① A. 1/2 B. 1 C. 2 D. 4 【129，7，1】具有5个顶点的有向完全图有① C 条弧。 ① A. 10 B. 16 C. 20 D. 25 【130，7，1】在一个有6个顶点的有向完全图中，其弧的数量是① B 。 ① A. 36 B. 30 C. 15 D. 42 【131，7，1】在任一有向图中，所有顶点的入度之和一定等于所有顶点的出度之和。 ① A. 正确 A B. 不正确 【132，7，1】下列数据组织形式中，（D）的各个结点可以任意邻接。 A．集合B．树形结构C．线性结构D．图状结构 【133，7，2】对于一个具有n个顶点和e 条边的无向图，若采用邻接表表示，则表头向量的大小为① A ；邻接表中所有结点总数是②B 。 ① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. 2e C. e D. n+e 【134，7，2】关于有向图的邻接表和逆邻接表表示法，下列结论①D 比较正确。 ① A. 用邻接表表示法计算入度比较方便 B. 用邻接表表示法计算入度和出度都方便 C. 用逆邻接表表示法计算入度和出度都不方便 D. 用逆邻接表表示法计算入度比计算出度方便 【135，7，2】关于图的邻接矩阵，下列结论① C 是正确的。 ① A. 有向图的邻接矩阵总是不对称的 B. 无向图的邻接矩阵总是不对称的 C. 有向图的邻接矩阵可以是对称的，也可以是不对称的 D. 无向图的邻接矩阵可以是不对称的，也可以是对称的 【136，7，2】邻接表是图的一种（B） A．顺序存储结构B．链式存储结构C．索引存储结构D．散列存储结构 【137，7，2】设n个顶点e条边的图G 用邻接表存储，则求每个顶点入度的时间复 16 17 杂度为（ B ）。 A. O(n) B. O(n+e) C. O(n*n) D. O(n*e) 【138，7，2】下面关于图的存储的叙述中，哪一个是正确的。A A ．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 B ．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关 C ．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 D ．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 【139，7，2】用邻接矩阵表示图所用的存储空间大小与图的边数成正比。 A. 正确 B. 不正确 B 【140，7，2】数据结构中Dijkstra 算法用来解决（ B ）问题。 A. 关键路径 B. 最短路径 C. 拓扑排序 D. 字符串匹配 【141，7，3】已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍 历，则可能得到的一种顶点序列为 ① D 。 ????????? ???????????010100101101010010110001001001010110 ① A. V1,V2,V3,V4,V5,V6 B. V1,V3,V5,V2,V4,V6 C. V1,V3,V5,V6,V4,V2 D. V1,V2,V4,V5,V6,V3 【142，7，3】图的深度优先遍历类似于二叉树的 ①A 。 ① A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 【143，7，3】在用邻接表表示图时，深度优先遍历算法的时间复杂度为（ B ） A. O （n ） B. O （n+e ） C. O （n2） D. O （n3） 【144，7，3】 如果无向图G 必须进行二次广度优先搜索才能访问其所有顶点，则下列 说法中不正确的是（ C ） A ．G 肯定不是完全图 B ．G 一定不是连通图 C ．G 中一定有回路 D ．G 有2个连通分量 【145，7，3】如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点， 则该图一定是（A ）。 A. 连通图 B. 完全图 C. 有回路的图 D. 一棵树 【146，7，3】连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。 A. 正确A B. 不正确 【147，7，4】下列关于图的生成树的唯一性，正确的是C①。 ① A. 生成树是唯一的 B. 生成树是不唯一的 C. 生成树是唯一性不确定 D. 图的生成树有两棵 【148，7，4】关于无向连通图的最小生成树的个数，B①。 ① A. 一定有多棵 B. 一定只有一棵 C. 有一棵或多棵 D. 可能不存在 【149，7，4】一个无向图的最小生成树的个数， C ①。 ① A. 一定有多棵 B. 一定只有一棵 C. 有一棵或多棵 D. 可能不存在 【150，7，5】在AOE网中，关键路径就是其中从源点到汇点的一条最长的路径。 ① A. 正确A B. 不正确 【151，7，5】下图为AOV网，其可能的拓扑有序序列为（ B ）。 A. ACBDEF B. ACBEDF C. ABCEFD D. ABCDFE 【152，9，1】对线性表进行二分查找时，要求线性表必须① B 。 ① A. 以顺序方式存储 B. 以顺序方式存储且元素有序 C. 以链式方式存储 D. 以链式方式存储且元素有序 【153，9，1】关于判定树，下列说法不正确的是①C 。 ① A. 判定树是对有序序列进行二分查找得到的树 B. n个结点的判定树的深度为[log2n]+1 18 19 C. 判定树的叶子结点都在同一层 D. 判定树除去最后一层结点以后是满二叉树或空二叉树 【154，9，1】若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值 位于中间值的前面，下次的查找区间为从原开始位置至（ B ） A ．该中间位置 B ．该中间位置－1 C ．该中间位置＋1 D ．该中间位置／2 【155，9，1】从原理上讲，折半查找法要求查找表中各元素的键值必须是 （ A ） 。 A. 递增或递减 B. 递增 C. 递减 D. 无序 【156，9，1】 在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法 查找关键码12需做（ C ）次关键码比较。 A.2 B.3 C.4 D.5 【157，9，1】折半查找算法的时间复杂度是（C ）。 A. O(n 2) B. O(n) C. O(log 2n) D. O(nlog 2n) 【158，9，2】 分别以下列序列构造二叉排序树，则与其它几个序列构造的结果不同的 是（ C ） A. （80，70，60，75，90，85，100，10） B. （80，90，85，70，60，10，75，100） C. （80，90，70，85，10，60，75，100） D. （80，90，100，70，85，60，10，75） 【159，9，2】如果某二叉树的左右子树的高度差的绝对值不大于1，则一定是平衡二叉 树。 ① A. 正确A B. 不正确 【160，9，2】若构造一棵具有n 个结点的二叉排序树，最坏的情况下其深度不会超过 （ B ）。 A ．n/2 B ．n C ．(n+1)/2 D ．n+1 【161，9，2】下面哪些二叉树是A VL 树（ C ）。 （1）（2）（3）（4） A. （1）（3） B.（2）（3） C.（3） D.（1）（4） 【162，9，2】A VL树的任何子树都是A VL树。 A. 正确A B. 不正确 【163，9，3】在散列表中，所谓同义词就是具有相同散列地址的两个元素。 ① A. 正确A B. 不正确 【164，9，3】对包含N个元素的散列表进行查找，平均查找长度( D ) 。 A.为O(log2N) B.为O(N) C.不直接依赖于N D.上述三者都不是 【165，10，0】在下列排序算法中，时间复杂度不受数据初始特性影响，恒为O(n2)的是（ B ）。 A. 插入排序 B. 冒泡排序 C. 选择排序 D. 堆排序 【166，10，0】若要求尽可能快地对实数数组进行稳定的排序，则应选(C)。 A.快速排序 B.堆排序 C.归并排序 D.基数排序 【167，10，0】下列排序算法的时间复杂度最小的是（D）。 A．冒泡排序 B. 希尔排序 C. 简单选择排序 D. 归并排序 【168，10，0】设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（C）排序法。 A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序 【169，10，2】排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为①C 。 ① A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序 【170，10，2】插入排序算法在每一趟都能选取出一个元素放在其最终的位置上。 ① A. 正确 B. 不正确 B 【171，10，2】直接插入排序是不稳定的排序方法。 A. 正确 B. 不正确B 【172，10，3】快速排序方法在①C 情况下最不利于发挥其长处。 ① A. 要排序的数据量太大 B. 要排序的数据在含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 20 Java数据结构和算法 一、数组于简单排序 (1) 二、栈与队列 (4) 三、链表 (7) 四、递归 (22) 五、哈希表 (25) 六、高级排序 (25) 七、二叉树 (25) 八、红—黑树 (26) 九、堆 (36) 十、带权图 (39) 一、数组于简单排序 数组 数组（array）是相同类型变量的集合，可以使用共同的名字引用它。数组可被定义为任何类型，可以是一维或多维。数组中的一个特别要素是通过下标来访问它。数组提供了一种将有联系的信息分组的便利方法。 一维数组 一维数组（one-dimensional array ）实质上是相同类型变量列表。要创建一个数组，你必须首先定义数组变量所需的类型。通用的一维数组的声明格式是：type var-name[ ]; 获得一个数组需要2步。第一步，你必须定义变量所需的类型。第二步，你必须使用运算符new来为数组所要存储的数据分配内存，并把它们分配给数组变量。这样Java 中的数组被动态地分配。如果动态分配的概念对你陌生，别担心，它将在本书的后面详细讨论。 数组的初始化（array initializer ）就是包括在花括号之内用逗号分开的表达式的列表。逗号分开了数组元素的值。Java 会自动地分配一个足够大的空间来保存你指定的初始化元素的个数，而不必使用运算符new。 Java 严格地检查以保证你不会意外地去存储或引用在数组范围以外的值。Java 的运行系统会检查以确保所有的数组下标都在正确的范围以内（在这方面， Java 与C/C++ 从根本上不同，C/C++ 不提供运行边界检查）。 多维数组 在Java 中，多维数组（multidimensional arrays ）实际上是数组的数组。你可能期望，这些数组形式上和行动上和一般的多维数组一样。然而，你将看到，有一些微妙的差别。定义多维数组变量要将每个维数放在它们各自的方括号中。例如，下面语句定义了一个名为twoD 的二维数组变量。 int twoD[][] = new int[4][5]; 简单排序 简单排序中包括了：冒泡排序、选择排序、插入排序； 1.冒泡排序的思想： 假设有N个数据需要排序，则从第0个数开始，依次比较第0和第1个数据，如果第0个大于第1个则两者交换，否则什么动作都不做，继续比较第1个第2个…，这样依次类推，直至所有数据都“冒泡”到数据顶上。 冒泡排序的的java代码： Public void bubbleSort() { int in,out; for(out=nElems-1;out>0;out--) for(in=0;in 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （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．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 《数据结构与算法设计》 实验报告 ——实验二 学院：自动化学院 班级： 学号： ： 一、实验目的 按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。 二、实验容 简单计算器。 请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求： ①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 ②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取 整。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 概要设计 1、宏定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 2、基本函数： （1）void InitStack_char(SqStack *S) //char型栈初始化 （2）void InitStack_int(sqStack *S) //int型栈初始化 （3）void Push_char(SqStack *S,char ch) //char型元素进栈 （4）void Push_int(sqStack *S,int num) //int型元素进栈 （5）char GetTop_char(SqStack *S) //取char型栈顶元素 （6）int GetTop_int(sqStack *S) //取int型栈顶元素 （7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回 （8）char Precede(char a,char b) //判断两运算符的先后次序 （9）Status Pop_char(SqStack *S,char &x) //char型栈出栈 （10）Status Pop_int(sqStack *S,int &x) //int型栈出栈 （11）int Operate(int a,char theta,int b) //计算a和b运算结果 3、流程图 《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图 西安科技大学 2013年硕士研究生入学考试试题A ───────────────────────────────── 科目编号：824 科目名称： 数据结构与算法设计 考生须知： 1、 答案必须写在答题纸上，写在试题或草稿纸上不给分。 2、 答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。 3、 答题必须写清题号，字迹要清楚，卷面要保持整洁。 4、 试题要随答题纸一起交回。 一、单项选择题（每小题2分，共30分） （1）并归排序的时间复杂度是（ ）。 A ．O(n 2) B ．O(nlog 2n) C ．O(n) D ．O(log 2n) （2）设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（ ）存储结构最节省时间。 A ．单链表 B ．单循环链表 C ．带尾指针的单循环链表 D ．带头结点的双循环链表 （3）散列文件是一种（ ）。 A ．顺序文件 B ．索引文件 C ．链接文件 D ．计算机寻址文件 （4）常用于函数调用的数据结构是（ ）。 A ．栈 B ．队列 C ．数组 D ．链表 （5）两个矩阵sn ms B A ,相乘的时间复杂度是（ ）。 A ．O(n 2) B ．O(s 2) C ．O(msn) D ．O(mn) （6）图的广度优先搜索遍历使用的数据结构是（ ）。 A ．栈 B ．队列 C ．集合 D ．树 （7）在单链表中，每个存贮结点有两个域，即数据域和指针域，指针域指向该结点的（ ）。 A ．直接前驱 B ．直接后继 C ．开始结点 D ．终端结点 （8）在已知头指针的单链表中，要在其尾部插入一个新结点，其时间复杂度是（ ）。 A ．O(n 2) B ．O(1) C ．O(n) D ．O(log 2n) （9）在链队列中执行入队操作，（ ）。 A ．需判断队是否为空 B ．限定在链表头p 进行 C ．需判断队是否为满 D ．限定在链表尾p 进行 （10）对序列（95，83，62，70）进行冒泡排序（由小到大），第2趟排序后的结果为（ ）。 A ．（70，83，62，95） B ．（70，62，83，95） 四川大学期末考试试题 （2008-2009学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师： 1．数据类型为（）。 A）数据项的集合B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合D）关键字的集合 2．链表不具有的特点是（）。 A）可随机直接访问任一元素B）插入删除不需要移动元素 C）不必事先估计元素个数D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵A nxn压缩存储在一维数组B[m]中，则m的值至少为（）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A）2k-1-1 B）2k-1C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGH IJ 中序序列：CBEDAGHFJI 注：试题字迹务必清晰，书写工整。本题2页，本页为第1页 教务处试题编号： 数据结构与算法课程设计报告 题目 两两相连的房间问题： 一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？ 问题分析 此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。 实现本程序需要解决以下问题： 1.如何表示每一个房间，即存储房间的信息，并且还要确定这所房子里的各个房间的位置。 2.各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。 3.从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。 4.为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只 访问未走过的房间。 5.最后通过什么的遍历方式才能判断各个房间之间是否互相相通。 数据结构的选择和概要设计 通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a 房间的，从而可知该图为有向图，那么门就相当于有向图中的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。 对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。定义一个全局的整形变量flag，如果是连通图的话则flag=1，否则flag=0。 程序实现的流程图如下： 北京交通大学考试试题（A卷） 课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为 的数据结构。 2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。 3. 直接插入排序用监视哨的作用是。 4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算 是。 5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有。 6. 在AOV网中，顶点表示，边表示。 7. 有向图G可进行拓扑排序的判别条件是。 8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行 Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。 二、选择题（每空2分，共20分） 1.在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法B．孩子链表表示法 C．孩子兄弟表示法D．顺序存储表示法 2.查找n个元素的有序表时，最有效的查找方法是（）。 A．顺序查找B．分块查找 C．折半查找D．二叉查找 3.将所示的s所指结点加到p所指结点之后，其语句应为（）。 p (A) s->next=p+1 ; p->next=s; (B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s; 4. 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。 A. 顶点v 的度 B. 顶点v 的出度 C. 顶点v 的入度 D. 依附于顶点v 的边数 5. 算法的时间复杂度为O （nlog 2n ）、空间复杂度为O(1)的排序算法是（ ）。 A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择 6. 设矩阵A 是一个对称矩阵，为了节省存储，将其 下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i ≤j), 在一维数组B 中下标k 的值是（ ）： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j 7. 由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下，查找成功的平均查找长度是（ ）。 A ．29/11 B. 31/11 C. 33/11 D.35/11 8. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。 A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为 （ ）。 A ．5 B ．6 C ．7 D ．8 三、 判断题（10分，每小题1分） 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 2. 数组不适合作任何二叉树的存储结构。（ ） 3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（ ） 4. 在含有n 个结点的树中，边数只能是n-1条。（ ） 5. 所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。（ ） 6. 简单选择排序在最好情况下的时间复杂度为O(n)。（ ） 7. 在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ） 8. 采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置 空，因为这会影响以后的查找。（ ） 9. 有n 个数存放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无 ?????? ? ???? ? ??=n n n n a a a a a a A ,2,1,2 ,21,21 ,1Λ Λ 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; 《数据结构与算法分析》课程设计教学任务书 一、课程设计的目的 数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 二、课程设计的基本要求 1. 独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 2. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 3. 按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成： a）需求分析： 在该部分中叙述，每个模块的功能要求 b）概要设计： 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） c）详细设计： 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组程序，每个功能模块采用不同的函数实现） 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释 d）调试分析： 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些，问题如何解决？），算法的改进设想 课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 4. 实现的结果必须进行检查和演示，程序源代码和程序的说明文件必须上交，作为考核内容的一部分。（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“09201199王五”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收 数据结构与算法试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的 B 部分地址必须就是连续的 C 一定就是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数 组至少需要的存储字数就是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。 10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为front与rear,则当前队列中的元素个数就是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 广西科技大学2015 —2016 学年第 1 学期课程考核试题试卷 考核课程数据结构与算法（ B 卷）考核班级物联网141 学生数36 印数40 考核方式闭卷考核时间120 分钟 一、单项选择题（在每小题的四个备选答案中，选出一个正确答案。每小题1分，共33分） 1、算法是（）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 2、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第8个元素的存储地址是（）。 A. 102 B. 104 C. 106 D. 108 3、在一个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i+1 4、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（）。 A. p指向头结点 B. p指向尾结点 C. p的直接后继是头结点 D. p的直接后继是尾结点 5、在以下的叙述中，正确的是（）。 A. 线性表的顺序存储结构优于链表存储结构 B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D. 线性表的链表存储结构优于顺序存储结构 6、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（）。 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; 7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。 A. p->next=q; q->prior=p; p->next->prior=q; q->next=q; B. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D. q->next=p->next; q->prior=p; p->next=q; p->next=q; 8、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。 A. p=p->next; B. p->next=p->next->next; C. p->next=p; D.p=p->next->next; 9、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 10、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。 A. O(1) B. O(n) C. O(m) D. O(m+n) 11、线性表的顺序存储结构是一种（）存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 12、循环链表的主要优点是（）。 A. 不再需要头指针 B. 已知某结点位置后能容易找到其直接前驱 C. 在进行插入、删除运算时能保证链表不断开 D. 在表中任一结点出发都能扫描整个链表 13、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）。 常用的大数据结构与算法 在学习了解这些数据结构和算法之前，引用一位前辈的话： “我们不需要你能不参考任何资料，实现红黑树；我们需要的是你能在实践当中，选择恰当的数据结构完成程序开发；在必要的时候，能在已有的数据结构基础上进行适当改进，满足工程需要。但要做到这一点，你需要掌握基础的算法和数据结构，你需要理解并应用一些高级数据结构和算法的思想。因此，在程序员这条道路上，你要想走得更远，你需要活用各种数据结构，你需要吸收知名算法的一些思想，而不是死记硬背算法本身。” 那么，工程实践当中，最常用的算法和数据结构有哪些？ 以下是Google工程师Arjun Nayini在Quora给出的答案，得到了绝大多数人的赞同。 最常用的算法 1.图搜索算法(BFS,DFS) 2.排序算法 3.通用的动态规划算法 4.匹配算法和网络流算法 5.正则表达式和字符串匹配算法 最常用的数据结构 1.图，尤其是树结构特别重要 2.Maps结构 3.Heap结构 4.Stacks/Queues结构 5.Tries树 其他一些相对比较常用的数据算法还有：贪心算法、Prim’s / Kruskal’s算法、Dijkstra’s 最短路径算法等等。 怎么样才能活用各种数据结构？ 你能很清楚的知道什么时候用hash表，什么时候用堆或者红黑色？在什么应用场景下，能用红黑色来代替hash表么？要做到这些，你需要理解红黑树、堆、hash表各有什么特性，彼此优缺点等，否则你不可能知道什么时候该用什么数据结构。 常言道： 程序=算法＋数据结构 程序≈数据结构 小编希望这些算法的掌握能够帮助大家拓宽握数据结构和算法的视野，提高算法设计和动手编程的能力。Java数据结构和算法
数据结构与算法习题及答案
数据结构与算法基础知识总结
数据结构与算法设计实验
数据结构与算法C语言版期末复习题
数据结构与算法复习题10(C语言版)
824数据结构与算法设计A
计算机学院数据结构与算法分析期末试题(2007级B)_无答案
大数据结构与算法课程设计程序及报告材料
北京交通大学数据结构与算法期末测验考试参考答案
数据结构与算法分析习题与参考答案
天津科技大学数据结构与算法课程设计
数据结构与算法试题
数据结构与算法设计知识点
数据结构与算法试卷(B卷)
常用的大数据结构与算法