当前位置：文档之家 › 数据结构作业-1-1

数据结构作业-1-1

  • 格式：ppt
  • 大小：451.50 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

数据结构形考作业1

数据结构形考作业1

一、单项选择题（每小题2分，共40分）题目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。

分析算法的易懂性和文档性算法指的是（）。

选择一项：A. 计算机程序B。

排序方法C。

解决问题的计算方法D. 解决问题的有限运算序列题目8算法的时间复杂度与( ）有关。

选择一项:A. 数据结构B。

算法本身C。

计算机的操作系统D。

所使用的计算机题目9设有一个长度为n的顺序表，要在第i个元素之前(也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为( ）。

选择一项：A。

n—iB. iC。

n-i—1D。

n—i+1题目10设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为( ）。

选择一项:A. n-iB。

n-i+1C。

n—i—1D。

i题目11在一个单链表中,p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点,可用语句（)。

选择一项:A。

q-〉next=NULLB. p-〉next=q->nextC. p-〉next=qD。

p=q—>next题目12在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。

数据结构作业

数据结构作业

第六章树和二叉树
6.45 编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
6.46 编写复制一棵二叉树的非递归算法。
6.59 编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中所有的边（这里的边是指树T本身的分支，而不是孩子兄弟链表所形成的二叉树的分支）。输出的形式为（k1, k2）, ..., (ki, kj), ..., 其中，ki和kj为树结点中的结点标识。
1.20试编写算法求一元多项式 的值Pn(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai（i=0, 1,…, n）、x0和n，输出为Pn(x0)。
第二章线性表
2.11设顺序表va中的数据元素非递减有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
注：根据同学们的要求，将作业量从六道题减少到三道题，希望同学们能及时完成。
第五章数组和广义表
5.21 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组C存放结果矩阵。
5.26 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。
5.33 试编写递归算法，输出广义表中所有原子项及其所在的层次。
第十二章 文件
12.10假设某个有3000张床位的旅店需建立一个便于管理的文件,每个记录是一个旅客的身份和投宿情况。其中旅客身份证号(15位十进制数字)可作为主关键字，此外还需建立按姓名、投宿日期、从哪来等次关键字项索引。请为此文件确定一种组织方式(如:主文件如何组织,各次关键字项索引如何建立等
第十章 排序
10.23 试以L.r[k+1]作为监视哨改写直接插入排序算法。其中，L.r[1...k]为待排记录且k<MAXSIZE。
北语 18秋《数据结构》 作业1234

北语 18秋《数据结构》 作业1234

18秋《数据结构》作业_1一、单选题 ( 每题4分, 共23道小题, 总分值92分 )1.答案：B作业代做QQ：805009261 成绩保证95分以上，基本满分！2.答案：B3.答案：D4.答案：D5.与单链表相比，双链表的优点之一是___。

A. 插入、删除操作更简单B. 可以进行随机访问C. 可以省略表头指针或表尾指针D. 顺序访问相邻结点更灵活答案：D6.数据结构在计算机内存中的表示是指___。

A. 数据的存储结构B. 数据结构C. 数据的逻辑结构D. 数据元素之间的关系7.快速排序在下列情况下最易发挥其长处的是（）。

A. 被排序的数据中含有多个相同排序码B. 被排序的数据已基本有序C. 被排序的数据完全无序D. 被排序的数据中的最大值和最小值相差悬殊8.A. (A)B. (B)C. (C)D. (D)9.链式栈与顺序栈相比，一个比较明显的优点是（）。

A. 插入操作更加方便B. 通常不会出现栈满的情况C. 不会出现栈空的情况D. 删除操作更加方便10.11.12.13.有一个有序表{1,3,9,12,32,41,45,62,75,77,82,95,100}，当折半查找值为82的结点时，___次比较后查找成功。

A. 11B. 5C. 4D. 814.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有___个空指针域。

A. 2m-1B. 2mC. 2m+1D. 4m15.A. (A)B. (B)C. (C)D. (D)16.A. (A)B. (B)C. (C)D. (D)17.A. (A)B. (B)C. (C)D. (D)18.下述哪一条是顺序存储结构的优点___。

A. 插入运算方便B. 可方便地用于各种逻辑结构的存储表示C. 存储密度大D. 删除运算方便19.设某棵二叉树中有2000个结点，则该二叉树的最小高度为___。

A. 9B. 10C. 11D. 1220.设一组初始记录关键字序列为（345,253,674,924,627），则用基数排序需要进行___趟的分配和回收才能使得初始关键字序列变成有序序列。

大工15秋《数据结构》在线作业1满分答案

大工15秋《数据结构》在线作业1满分答案

大工15秋《数据结构》在线作业1满分答案大工15秋《数据结构》在线作业1一单选题1.广义表((e))的表头是（）。

A. eB. (e)C. ()D. (())正确答案：B2.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。

A. 1B. 2C. 3D. 4正确答案：B3.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。

A. (n+1)/2B. n/2C. nD. n+1正确答案：C4.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。

A. head==NULLB. head→next==NULLC. head→next==headD. head!=NULL正确答案：B5.一个顺序栈S，元素a，b，c，d，e依次进栈，如果5个元素的出栈顺序为b，e，d，c，a，则顺序栈的容量至少应为（）。

A. 2B. 3C. 4D. 5正确答案：C6.在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动（）个数据元素。

A. (n-1)/2B. n/2C. n-1D. n正确答案：B7.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（）。

A. cB. b，cC.（b，c）D.（（b，c））正确答案：D8.表达式a*(b+c)-d的后缀表达式是（）。

A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd精确谜底：B9.在一个单链表中，删除*p结点之后的一个结点的操作是（）。

A. p->next=p;B. p->next->next=p->next;C. p->next->next=p;D. p->next=p->next->next;精确谜底：D10.最大容量为n的轮回行列，队尾指针是rear，队头是front，则队空的条件是（）。

数据结构作业题及答案

数据结构作业题及答案

数据结构作业题及答案第一章绪论1、简述下列概念：数据、数据元素、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

数据：指能够被计算机识别、存储和加工处理的信息载体。

数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。

数据元素有时可以由若干数据项组成。

数据结构：指的是数据之间的相互关系，即数据的组织形式。

一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

逻辑结构：指各数据元素之间的逻辑关系。

存储结构：就是数据的逻辑结构用计算机语言的实现。

线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

2、常用的存储表示方法有哪几种?顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

由此得到的存储表示称为顺序存储结构。

链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。

由此得到的存储表示称为链式存储结构。

索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

3、求解下列算法的时间复杂度(1)i=1;k=0 while(i<n){k=k+10*i;i++;}T(n)=n-1∴T(n)=O(n)这个函数是按线性阶递增的(2)i=0;k=0;do{k=k+10*i;i++;} while(i<n);T(n)=n∴T(n)=O(n)这也是线性阶递增的(3)i=1;j=0;while(i+j<=n) {if(i<j)j++; else i++;}T(n)=n/2∴T(n)=O(n)虽然时间函数是n/2,但其数量级仍是按线性阶递增的。

200721数据结构 作业(高起专、高起本)

200721数据结构 作业(高起专、高起本)


比较（
）个元素结点。
A、
B、n
C、
D、
20、设单链表中指针 p 指向结点 m，若要删除 m 之后的结点（若存在），则需修改指针的操作
为（
）。
A、
B、
C、
D、
21、在（
）运算中，使用顺序表比链表好。
A、插入
B、删除
C、根据序号查找
D、根据元素值查找
22、在一个具有 n 个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度
第 2 页 共 20 页 在您完成作业过程中，如有疑难，请登录学院网站“辅导答疑”栏目，与老师进行交流讨论！
C、一个无限序列，可以为空
D、一个无限序列，不可以为空
18、在一个长度为 n 的顺序表中删除第 i 个元素
时，需向前移动（
）个元素。
A、
B、
C、
D、i
19、从一个具有 n 个结点的单链表中查找其值等于 x 的结点时，在查找成功的情况下，需平均
（ ）个。
第 6 页 共 20 页 在您完成作业过程中，如有疑难，请登录学院网站“辅导答疑”栏目，与老师进行交流讨论！
A、15
B、16
C、17
D、47
48、设 n , m 为一棵二叉树上的两个结点，在中序遍历序列中 n 在 m 前的条件是（ ）。
A、n 在 m 右方
B、n 在 m 左方
C、n 是 m 的祖先
D、求串长
6、二维数组 M 的成员是 6 个字符（每个字符占一个存储单元）组成的串，行下标 i 的
范围从 0 到 8，列下标 j 的范围从 1 到 10，则存放 M 至少需要（
）个字节。
A、90
B、180
数据结构 第一次作业 测验答案 慕课答案 作业一 UOOC优课 课后练习 深圳大学

数据结构 第一次作业 测验答案 慕课答案 作业一 UOOC优课 课后练习 深圳大学

数据结构第一次作业一、单选题 (共100.00分)1. 已知栈S为空，数据1、2、3、4依次逐个进入栈S，则栈顶数据为（）A. 1B. 2C. 3D. 4正确答案：D2. 栈的最大特点是（）A. 先进先出B. 后进先出C. 无限递归D. 有限递归正确答案：B3. 队列的最大特点是（）A. 先进先出B. 后进先出C. 无限递归D. 有限递归正确答案：A4. 已知栈包含10元素，其中存放在栈底是第1号元素，则第10号元素可以通过（）进行访问A. 栈底B. 栈中C. 栈尾D. 栈顶正确答案：D5. 以下结构中，哪一个是属于物理结构（）A. 栈B. 队列C. 链队列D. 线性表正确答案：C6. 使用长度为10的数组实现循环队列，则该队列最多存储数据个数为（）A. 1B. 9C. 11.D.5正确答案：B7. 已知顺序表包含1000个数据，现在第88号位置插入新的数据，需要移动的数据个数为（）A. 88B. 87C. 912D. 913正确答案：D8. 若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是（）A. 单链表B. 双链表C. 单循环链表D. 顺序表正确答案：D9. 以下结构中，哪一个是属于物理结构（）A. 线性表B. 栈C. 单链表D. 队列正确答案：C10. 已知顺序表包含100个数据，现在要删除第99号位置的数据，需要移动的数据个数为（）A. 99B. 100C. 1D. 2正确答案：C已知指针p指向单链表L的某个结点，判断p指向的结点是尾结点的条件是（）A. if (p->next>p)B. if (p->next==NULL)D. if (p->data==0)正确答案：B12. 以下描述哪个是正确的（）A. 线性表的数据元素的存储位置一定是连续的B. 顺序表的数据元素的存储位置一定是连续的C. 链表的数据元素的存储位置一定不是连续的D. 线性表的数据元素的存储位置一定不是连续的正确答案：B已知顺序表包含100个数据，先在第15号位置插入1个新数据，接着删除第3号位置的数据，需要移动的数据总个数为（）A. 18B. 84C. 184D. 188正确答案：C在数据结构概念中，数据的基本单位是（）A. 数据段B. 数据项C. 数据表D. 数据元素D在数据结构概念中，结构是描述（）A. 数据项的类型B. 数据元素之间的关系C. 数据成员的先后顺序D. 数据对象的取值范围正确答案：B在算法设计中，要求算法便于理解和修改是属于算法要求的（）A. 正确性B. 可读性C. 健壮性D. 效率高正确答案：B以下关于算法的描述，哪个是正确的（）A. 算法可以没有输入B. 算法可以包含无限个执行步骤C. 算法可以没有输出D. 算法的每个步骤允许带有歧义的正确答案：抽象数据类型ADT通过三方面描述，包括数据关系、数据操作和（）A. 数据对象B. 数据来源C. 数据范围D. 数据判断正确答案：A设n为问题规模，以下程序的时间复杂度为（）for (i=1; i<=10000; i++) for (j=1; j<=n; j++) a = a + 1;A. O(1)B. O(n)C. O(10000n)D. O(n2)正确答案：B20.设n为问题规模，以下程序的时间复杂度为（） for (i=1; i< POW（2, n）; i++) //POW(x, y)函数表示x的y次幂a = a+100;A. O(n)B. O(2n)C. O(n!)D. O(2n)正确答案：D。

数据结构实践作业

数据结构实践作业

数据结构作业利用单向链表数据结构完成对链表的如下操作:1、创建一条含整数结点的无序链表2、链表结点的输出3、链表结点的升序排序4、分别计算链表中奇数和偶数结点之和并输出5、释放链表具体要求将程序功能做成菜单，形式如下：1、创建一条含整数结点的无序链表2、链表结点的输出3、链表结点的升序排序4、分别计算链表中奇数和偶数结点之和并输出5、释放链表0、退出《数据结构》大作业1 总体要求将程序功能做成菜单，形式如下：（1）创建一条含整数结点的无序链表（2）链表结点的输出（3）链表结点的升序排序（4）分别计算链表中奇数和偶数结点之和并输出（5）释放链表2 开发环境软件环境：Window10，Visual Studio 20173 系统运行效果截图（1）主菜单：（2）创建一条含整数结点的无序链表：3,6,2,5,9（3）链表结点的输出（4）链表结点的升序排序（5）分别计算链表中奇数和偶数结点之和并输出（6）释放链表4 源程序#include<iostream>//头文件using namespace std;//节点数据结构定义struct node{int data;node *next;};//创建一条含整数结点的无序链表node *CreateLinkList(){node *p1, *p2, *head;int n;p2 = NULL;head = NULL;cout <<"正在创建一个无序链表\n";cout <<"请输入一个整数，以-1结束：";cin >> n;//循环输入一个整数，直到数值为-1结束，创建一条无序链表while (n != -1){p1 = new node;p1->data = n;//采用尾插法，新建一个结点并连接到链表尾部if (head == 0){head = p1; p2 = p1; //首结点的建立}else{p2->next = p1; p2 = p1;}cout <<"请输入一个整数，以-1结束：";cin >> n;}if (head != 0) //尾结点p2->next = 0;return(head);}//输出结点void PrintLinkList(const node *head){const node *p;p = head;while (p != NULL){cout <<" "<< (p->data);p = p->next;}cout << endl;}//升序排序void SortLinkList(node *head){node temp;node *p = NULL;node *q = NULL;//判断结点为空或者只有一个结点if (head == NULL || head->next == NULL){return;}//p->next!=NULL为链表倒数第2个结点for (p = head; p->next != NULL; p = p->next) {for (q = p->next; q != NULL; q = q->next){if (p->data > q->data) //升序{ //交换数据域temp.data = q->data;q->data = p->data;p->data = temp.data;}}}return;}//奇数结点和int OddSumLinkList(const node *head){int sum = 0;const node *p;p = head;while (p){//判断数值为是否奇数if (p->data % 2 != 0){sum = sum + p->data;}p = p->next;}return sum;}//偶数结点和int EvenSumLinkList(const node *head){int sum = 0;const node *p;p = head;while (p){//判断是否偶数if (p->data % 2 == 0){sum = sum + p->data; //偶数结点的数值累加}p = p->next;}return sum;}//释放链表void DeleteLinkList(node *head){node *p;while (head){p = head;head = head->next;delete p;}printf("释放成功\n");}void main(){node *head;head = NULL;int select;cout <<"************菜单************"<< endl;cout <<"输入对应选择，执行对应操作"<< endl;cout <<"1.创建一条含整数结点的无序链表"<< endl;cout <<"2.链表结点的输出"<< endl;cout <<"3.链表节点的升序排序"<< endl;cout <<"4.分别计算链表中奇数和偶数结点之和并输出"<< endl;cout <<"5.释放链表"<< endl;cout <<"0.退出"<< endl;while (1){cout <<"\n请输入选择：";cin >> select;switch (select) //判断选项，并执行对应的函数{case 1:{head = CreateLinkList();printf("无序链表创建完成\n");break;}case 2:{printf("输出链表中各结点数据：");PrintLinkList(head);break;}case 3:{SortLinkList(head);printf("升序后：");PrintLinkList(head);break;}case 4:{int oddsum;int evensum;oddsum = OddSumLinkList(head);evensum = EvenSumLinkList(head);printf("奇数和= %d，偶数和= %d\n", oddsum, evensum);break;}case 5:{DeleteLinkList(head);break;}case 0:{cout <<"退出"<< endl;exit(0);}default:{cout <<"输入选项有误，请重新输入："<< endl;break;}}}}。

数据结构的作业

数据结构的作业


第五章作业： 第五章作业： 1.假设有二维数组 假设有二维数组a:array[1..6,0..7] of elemtp; 每个数据元 假设有二维数组 素占6个字节 存储器按字节编址 的基地址为1000,则： 素占 个字节,存储器按字节编址。a的基地址为 个字节 存储器按字节编址。 的基地址为 则 (1) 数组 的体积； 数组a的体积 的体积； (2)数组 的最后一个元素的第一个字节的地址； 数组a的最后一个元素的第一个字节的地址 数组 的最后一个元素的第一个字节的地址； (3)按行存储时，a[2,4]的第一个字节的地址； 按行存储时， 的第一个字节的地址； 按行存储时 的第一个字节的地址 (4)按列存储时，a[5,7]的第一个字节的地址； 按列存储时， 的第一个字节的地址； 按列存储时 的第一个字节的地址
7.写出下列各树的先根序列 后根序列 并且画出对应的二 写出下列各树的先根序列,后根序列 写出下列各树的先根序列 后根序列,并且画出对应的二 叉树. 叉树 A A A A B C D B C B C I 8.画出第 题的森林相应的二叉树 画出第7题的森林相应的二叉树 画出第 题的森林相应的二叉树. 9.画出和下列已知序列对应的树 画出和下列已知序列对应的树T: 画出和下列已知序列对应的树 树的先根次序访问序列为:GFKDAIEBCHJ,而且 而且 树的先根次序访问序列为 树的后根次序访问序列为:DIAEKFCJHBG。 。 树的后根次序访问序列为 E F J G H K
3.用单链表实现 用单链表实现Locate(L,x)函数。（可参考 函数。（可参考P26算法 算法2.5) 用单链表实现 函数。（可参考 算法 4.上机题：设单链表Va中的数据元素递增有序。试编 上机题：设单链表 中的数据元素递增有序 中的数据元素递增有序。 上机题 写程序，将数据X插入单链表 插入单链表Va， 写程序，将数据 插入单链表 ，要求插 入后保持该表的有序性。 入后保持该表的有序性。 5.写出双向链表删除第i个结点的算法 5.写出双向链表删除第i个结点的算法。 写出双向链表删除第 个结点的算法。 6.写出求双向循环链表长度的算法。（注：头结点 写出求双向循环链表长度的算法。（注 写出求双向循环链表长度的算法。（ 不算） 不算）
奥鹏北语14秋《数据结构》作业1满分答案

奥鹏北语14秋《数据结构》作业1满分答案

A. 1,2,3
B. 9,5,2,3
C. 9,5,3
D. 9,4,2,3
?
正确答案：D
17.以下____不是队列的基本运算。
A.
从队尾插入一个新元素
B.
从队列中删除第i个元素
C.
判断一个队列是否为空
D.
读取队头元素的值
?
正确答案：B
18.下列关于数据结构基本概念的叙述中，正确的是______。
A.数据的逻辑结构分为表结构和树结构
B.数据类型
C.数据元素
D.数据变量
?
正确答案：C
7. A. A
B. B
C. C
D. D
?
正确答案：A
8.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为___。
A. 3
B. 4
C. 5
D. 1
?
正确答案：B
9.设有以下四种排序方法，则___的空间复杂度最大。
A.冒泡排序
B.快速排序
C.堆排序
D.希尔排序
?
正确答案：B
10.下面关于线性表的叙述错误的是___。
A.线性表采用顺序存储必须占用一片连续的存储空间
B.线性表采用链式存储不必占用一片连续的存储空间
C.线性表采用链式存储便于插入和删除操作的实现
D.线性表采用顺序存储便于插入和删除操作的实现
?
正确答案：D
11. A. A
B. B
?
正确答案：C
3.在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为___。
A. 4
B. 5
C. 6
D. 7
?
电子科技大学15秋《数据结构》在线作业1满分答案

电子科技大学15秋《数据结构》在线作业1满分答案

15秋《数据结构》在线作业1
一,单选题
1. 在计算机内实现递归算法时所需的辅助数据结构是（）。

A. 栈
B. 队列
C. 树
D. 图
正确答案：A
2. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。

A. 顺序表
B. 用头指针表示的单循环链表
C. 用尾指针表示的单循环链表
D. 单链表
正确答案：C
3. 判断两个串大小的基本准则是（）。

A. 两个串长度的大小
B. 两个串中首字符的大小
C. 两个串中大写字母的多少
D. 对应的第一个不等字符的大小
正确答案：B
4. 在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（）。

A. 0
B. 2
C. 3
D. 5
正确答案：C
5. 栈和队列都是（）。

A. 限制存取位置的线性结构
B. 顺序存储的线性结构
C. 链式存储的线性结构
D. 限制存取位置的非线性结构
正确答案：D
6. 设有两个串T和P，求P在T中首次出现的位置的串运算称作（）。

A. 联接
B. 求子串
C. 字符定位
D. 子串定位。

北语直属14秋《数据结构》作业1满分答案

作业名称：14秋《数据结构》作业1 出卷人：SA
作业总分：100 通过分数：60
起止时间：2015-1-21 10:20:21 至2015-1-22 9:11:26
学员姓名：学员成绩：100
标准题总分：100 标准题得分：100
详细信息：
题号:1 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:4.17 内容:
将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为___。

A、O（1）
B、O（n）
C、O（m）
D、O（m+n）
标准答案:C
学员答案:C
本题得分:4.17
题号:2 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:4.17 内容:
栈和队列的共同特点是___。

A、只允许在端点处插入和删除元素
B、都是先进后出
C、都是先进先出
D、没有共同点
标准答案:A
学员答案:A
本题得分:4.17
题号:3 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:4.17 内容:
图形:
A、(A)
B、(B)
C、(C)
D、(D)
标准答案:A
学员答案:A
本题得分:4.17。

大连理工大学《数据结构》作业 参考答案

u=q->link; q->link=L->link; L->link=q; q=u; } }
数据结构作业参考答案
//有序表插入 void yxcharu(LinkList &L, ElemType e) {
LinkList pre,p,s; pre=L; p=L->link; while(p&&p->data<e) {
pre=p; p=p->link; } s=(LinkList)malloc(sizeof(Lnode)); s->data=e; s->link=p; pre->link=s; }
main()
{
LinkList L;
int n,i,mink,maxk;
ElemType e;
char choice='0';
数据结构作业参考答案
if(InitList_Sq(L)) {
printf("建立空顺序表成功！\n"); do{
printf("当前线性表长度为：%d\n",L.length); printf("请输入要插入元素的位置："); scanf("%d",&i); printf("请输入要插入的元素值："); scanf("%d",&k); if(sxbcr(L,i,k)) {
s=(LinkList)malloc(sizeof(Lnode));
scanf("%d",&s->data); s->link=NULL;
p->link=s;
p=s;

数据结构作业及答案

第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

《数据结构》在线作业一

C.线性表采用链式存储便于插入和删除操作的实现
D.线性表采用顺序存储便于插入和删除操作的实现
40.数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是（）有限集合，R是D上的关系有限集合。
A.算法
B.数据元素
C.数据操作
D.数据对象
A.O(n)
B.O(n2)
C.O(n3)
D.O(n4 )
6.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。
A.s->next=p;p->next=s;
B.s->next=p->next;p->next=s;
C.s->next=p->next;p=s;
B.top= =0
C.top！=m0
D.top= =m0-1
11.在二叉排序树中插入一个结点的时间复杂度为（ ）。
A.O(1)
B.O(n)
C.O(log2n)
D.O(n2 )
12.设串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（）。
A.5
B.6
C.7
D.8
24.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。

南开24秋学期《数据结构》作业参考一

24秋学期《数据结构》作业参考1.堆的形状是一棵()选项A：二叉排序树选项B：满二叉树选项C：完全二叉树选项D：平衡二叉树参考答案：C2.用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的选项A：栈选项B：队列选项C：树选项D：图参考答案：A3.栈中元素的进出原则是（）选项A：先进先出选项B：后进先出选项C：栈空则进选项D：栈满则出参考答案：B4.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()选项A：79,46,56,38,40,84选项B：84,79,56,38,40,46选项C：84,79,56,46,40,38选项D：84,56,79,40,46,38参考答案：B5.有8个结点的无向图最多有（）条边选项A：14选项B：28选项C：56选项D：112参考答案：B6.链表是一种采用存储结构存储的线性表选项A：顺序选项B：链式选项C：星式选项D：网状参考答案：B7.下列关键字序列中，()是堆选项A：16,72,31,23,94,53选项B：94,23,31,72,16,53选项C：16,53,23,94，31,72选项D：16,23,53,31,94,72参考答案：D8.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。

选项A：20，70，30，50选项B：30，88，70，50选项C：20，50选项D：30，88，50参考答案：A9.已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（）选项A：0 2 4 3 1 5 6选项B：0 1 3 5 6 4 2。

数据结构作业题及参考答案【精选文档】

东北农业大学网络教育学院数据结构作业题(一)一、选择题（每题2分,共20分）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．在一棵树中,（）没有前驱结点.A、分支结点B、叶结点C、树根结点D、空结点4．在有向图中每个顶点的度等于该顶点的( ）。

A、入度B、出度C、入度与出度之和D、入度与出度之差5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( )的值除以9。

A、20B、18C、25D、226．下列程序段的时间复杂度为( ）。

s=0；for(i=1;i<n;i++)for(j=1；j〈n；j++）s+=i*j；A、O（1)B、O (n)C、O（2n）D、O（n2）7．栈是一种操作受限的线性结构，其操作的主要特征是（）。

A、先进先出B、后进先出C、进优于出D、出优于进8．假设以数组A[n］存放循环队列的元素，其头、尾指针分别为front和rear.若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）。

A、（rear-front—1)％nB、(rear—front)％nC、(front-rear+1）%nD、(rear—front+n)％n9．高度为5的完全二叉树中含有的结点数至少为（）。

A、16B、17C、31D、3210．如图所示有向图的一个拓扑序列是( )A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空题(每空1分,共20分)1．n (n﹥0）个顶点的无向图最多有条边,最少有条边。

2．在一棵A VL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过.3．已知8个数据元素为(34，76,45,18，26，54，92,65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
T.push(s[i]); while(!T.isEmpty())
{s1=T.pop();} if(s==s1) return true; else return false;
}
提示：若栈的入栈顺序与出栈顺序相同，则字符串s为回文
第十三次作业-图
1．采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（A）。
11.6 Show the BFS tree for the graph of Figure 11.26,starting at Vertex 1. 对于图11.26所示的图，给出其从顶点1开始的BFS树广度优先搜索树。 答案：
11.3（a）画出图11.26所示图的相邻矩阵
adjacency matrix 表示;
10.12给出把值1,2,3,4,5,6(按照这个顺序)插入图10.16中B+树的结果。
10.13给出把值18,19和20(按照这个顺序)插入图10.2(b)的B+树中删除 的结果。
10.15假定有一个B+树，它的内部节点，可以存储多达100个子女，叶 节点可以存储多达15条记录，对于1,2,3,4,和5层B+树，能够存储的最 大记录数和最小记录数是多少？
以此类推
期中考试：算法设计题：利用栈，判断一个字符串s是否是回文，若是返回1,否则返回0; 回文是指第一 个字符与最后一个相同，第二个字符与倒数第二个相同，依此类推。 如：“abba”是回文，“abab”不是回文。空串和长度为1的串都是回文。 可以直接使用如下定义中的基本操作。 栈的ADT定义如下：
第12-13作业 B B+树以及图
第十二次作业-图
10.8 给出把值55与46插入下图的2-3树中的结果。
10.9给定一组记录，其关键码值是字母，记录按照下面的顺序插入： C,S,D,T,A,M,P,B,W,N,G,U,R,K,E,H,O,L,J给出插入这些记录后的2-3树。
10.11给出把值55插入图10.17中B树的结果。
穷大； 处理完顶点4后，其相邻顶点的最短路径长度被更新为到4的直接距离； 再选定当前离4最近的顶点作为下一个顶点，再更新余下顶点的值； 依次类推；结果如下所示：
11.17对于11.26中的图，给出从顶点3开始使用Prim的MST(最小支撑树：包含所有顶 点以及一部分边的树，保证连通且所有权重最小)算法时各个边的访问顺序，并且给出 最终的MST。
分析：B+树中所有叶子节点在同一层，根节点最少有两棵子树，其余分支节点 的子树个数为[m/2]到m;也就是题目中的阶数m为100;
那么： 内部节点的孩子节点个数为：[50,100] 叶子节点的记录数为[1,15]
当层数为1时，根节点充当叶子节点，最少记录数为0，最多记录数为15； 当再来一个记录时，根节点要分裂为两层，变为内部节点，此时记录数16是 层数为2时最少的情况，最多的即为根节点和叶子节点均存满;
（a）
（b）
（c）邻接矩阵需要：36*2=72 bytes；邻接表需要：（6+18）*4+18* （2+2）=168 bytes。因此选择邻接矩阵更好。 （d）邻接矩阵需要：36*2=72 bytes；邻接表需要：（6+18）*4+18* （2+1）=150 bytes。因此选择邻接矩阵更好。
算法设计题： 计算一棵树的树叶结点的个数。树的存储采用Leftmost Child/Right Sibling存储方 式。 若你用C++实现，结点的类定义如下：
A）先序遍历 B）中序遍历 C）后序遍历
D）层次遍历
2．一个n个顶点的连通无向图，其边的个数至少为（A）。
A）n-1
B Show the DFS tree for the graph of Figure 11.26,starting at Vertex 1. 对于图11.26所示的图，给出其从顶点1开始的DFS树深度优先搜索树。 答案：
（b）画出这个图的邻接表adjacency list表示;
（c）如果每个指针需要4个字节，每个顶点的
标号占用两个字节，每条边的权需要两个字节，则
该图采用哪种表示方法需要的空间更多？
（d）如果每个指针需要4个字节,每个顶点的标
号需要一个字节，每条边的权需要两个字节，那么
采用哪种表示方法需要的空间更多？
count+=leavesCount(temp); return count }
第十四次作业-图
11.8对于11.26中的图，给出从顶点4开始出发，使用Dijkstra最短路径算法产生的最短 路径表，请向图11.19所示一样，每处理一个顶点时给出相应D值。
Dijkstra算法的流程为： 初始状态下，源顶点为4，除了顶点4，其余各个顶点的最短路径长度初值均为无
template <class T> class Stack { public: void clear(); bool push(const T item); bool pop(T&); bool topValue(T&); bool isEmpty(); bool isFull(); };
中期代码： bool checkString(string s) { Stack T; string s1=""; for(int i=0;i<s.length();i++)
class TreeNode{ public:
char val; //结点的值 TreeNode* LeftChild; //左孩子 TreeNode* RightSibling; //右兄弟 } 若你用C实现，结点的结构定义如下： struct TreeNode{ char val; //结点的值 struct TreeNode* LeftChild; //左孩子 struct TreeNode* RightSibling; //右兄弟 }
中期代码： int leavesCount(TreeNode *root) {
int count=0; if(root==null)return 0; if(root->leftchild==null)return 1; for(TreeNode *temp=root->LeftChild;temp;temp=temp->RightSibling)