数据结构算法问题_中华文本库
第1页/共2页
L其实是一个单循(即删除)算法.循符开始的j个字作为存储结构,递增有序,试写一算法删除顺序表中值重复多余的元素,得所得结果表中各元素值均不相同. 已知线性表的长度为N,试写一算法将线性表逆置
试写一算法,实现在线性表中找出最大值和最小值的元素及其所在位置
试写一个算法,将一个头结点指针为a的单链表A分解成两个单链表A和B,其中头结点指针分别为a和b,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表中序号为偶数的元素,并保持原来的相对顺序.
已知有一个单链表L(至少有一个结点),其头指针为head,试写一个算法将该单链表逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等 点数据域为整型的,而且是按从大到小顺序排列的循环链表(L为头结点指针,表非空),试写一算法插入一个结点S(其数据域为X)至循环链表的适当位置,使之保持链表的有序性.
环双链表,其结点类型结构包括3个域:prior, data和next,其中data为数据域,next为指针域,指向其后续结点,prior也为指针域,其值为空,因此,该双链表
环链表.试写一算法,将其修改为真正的双链表 设有两个顺序表A和B,且都递增有序,试写一算法,从A中删除与B中相同的那些元素(也就是计算A--B)
已知head是指向一个带头结点的单链表的头指针, p指向该链表的任一结点,试写一算法将p所指向的结点与其后续结点位置交换
已知两单链表A和B分别表示两个集合,其元素值递增有序,试写一算法求A和B的交集C,要求C同样以元素值递增的单链表形式存储. 设有一个带头结点的双向循环链表,head为链表的头指针,试写一算法,实现在值为x的结点之前插入一个值为y的结点. 利用顺序栈的基本运算,试设计一个算法,判断一个输入字符串是否具有中心对称(也就是所谓的”回文”,正读和反读均相同的字符系列),例如ababbaba, abcba都是中心对称的字符串.
已知函数:: fu(n)={n+1若n&2///////////////////fu([n/2])*fu([n/4])若n≥2}试写一个递归算法,实现其功能 假设用一个带头结点的循环单链表表示队列(称为循环链队列),该队列只设一个指向对尾结点的指针rear,不设头指针,试编写相应的入队(即插入)和出队
环链队列的结构如下图所示: 在队列中删除一个结点,首先要判断队列是否为空,若不为空,则可进行删除操作,否则显示出错.删除的思想是将原头结点删掉,把对头结点作为新的头结点,具体实现算法如下(要特别注意头结点和队头结点的区别)
法,实现输入一字符串,并检查串中是否含有圆括号,当圆括号匹配时逆序输出括号内的串,否给出出错信息. 队列(长度为K)存储,编写求斐波那契序列的前n(n&k)项(f0,f1,…fn--1)的算法,其函数定义如下:f(n)={0 n=0////// ///////// 1 n=1/////////////////// f(n--2)+f(n--1) n≥2
s1(顺序存储结构)中第k个字符起求出首次与字符串s2相同的子串的起始位置
从串s中删除所有与串t相同的子串
已知S和T是用结点大小为1的单链表存储的两个串,试设计一个算法找出S中第一个不在T中出现的字符 S和T是两个采用顺序结构存储的串,试写一个比较是否相等的函数,若相等则返回真值true,否则返回假值false.
序存储结构的串S,试写一算法删除S中第I个字
两个采用顺序结构存储的串,试写一个算法将串S中的第I个字符开始的j个字符用串T替换 ,实现顺序串的比较运算strcmp(S,T),当S&T时,函数值为1,当S==T时,函数值为0,当S&T时,函数值为-1
A中存在这样一个元素A[i][j]满足:A[i][j]是第I行元素中最小值,且又是第j列元素中最大值,则称此元素为该矩阵的一个马鞍点.假设以二维数组存储矩阵Am*n,试编写求出矩阵中所有马鞍点的算法
法,建立顺序存储稀疏矩阵的三元组表
已知A和B是两个n阶的对称矩阵,因为是对称矩阵,所以仅需要输入下三角元素值存入一维数组,试写一算法求对称矩阵A和B的乘积 采用链式存储结构,试写一个中序遍历二叉树的非递归算法 其算法思想也可以用指针数组来实现
为存储结构,试编写在二叉树中查找值为x的结点及求x所在结点在树中层数的算法
以二叉链表作为存储结构,试编写非递归的前序遍历二叉树的算法
试编写非递归的按层顺序遍历二叉树的算法 以中序线索而叉链表作为存储结构,试编写查找某结点* p的中序前驱结点的算法
以二叉链表作为存储结构,其根头指针为bt,试写从根开始层遍历二叉树的算法,同层的界点按从左至右的次序访问.
试编写一个实现连通图G的深度优先遍历(从顶点v出发)的非递归算法 试分别编写求DFS和BFS生成树的算法,要求打印出所有的树边..
以邻接表作图的存储结构,试编写在无向图中求顶点vi到vj之间的最短路径(vi≠vj)的算 37设计一个修改冒泡排序算法以实现双向冒泡排序的算法 38假设采用单链表作为存储结构,试编写一个直接选择排序(升序)的算法 按直接选择排序算法思想,交换结点的数据域和关键字域值的算法:
按直接选择排序算法思想,每次选择到最小的结点,将其脱链并加入到一个新链表中,这样可避免结点域值交换,最后将新链表的头指针返回.
已知一个已排序的记录文件用单链表表示,试写一算法,插入一个新记录,使得文件仍按关键字从小到大的次序排列. 序记录文件A[0..n-1]和B[0..m-1],试写一算法,将它们归并为一个有序文件,存放到C[0..m+n--1]中 试写一算法,利用二分查找算法在有序表R中插入一个元素x,并保持表的有序 试用C语言写出二分查找的递归算法
法,按降序输出二叉排序树(链式存储表示)上各结点的值.. 长为m,散列函数为H(K),用链地址法处理冲突.试编写输入一组关键字结构散列表的算法
---------------------链表,其结点的元素值以递增有序排列,试写算法删除该链表中多余的元素值相同的结点.
已知不带头结点的单循环链表L中有板有3个以上的结点,其结点的两个域分别为data和next,其中数据域data的类型为整型.设计算法以判断该链表中从第3个结点及其以后的每个结点的值是否等于其前面连续两个结点的值的和,若满足,返回true,否则返回false 树的根指针为T,以链式结构存储,试写出算法以输出二叉排序树中关键字最小的数据值
已知二叉树以链表方式存储,试写按层次遍历二叉树T的算法 已知T为一棵二叉排序树,
第1页/共2页
寻找更多 ""线性表，JS代码实现列表
&在日常生活中，我们经常使用列表：待办事项列表、购物清单、十佳榜单等。计算机程序也在使用列表，尤其是列表中保存的元素不是太多时。当不需要在一个很长的序列中查找元素，或者对其进行排序时，列表显得尤为有用。反之，如果数据结构非常复杂，列表的作用就没有那么大了。
&1.线性表的概念
&由零个或者多个数据元素组成的有限序列。
&线性表（亦作顺序表，List）是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素的类型相同，它们之间的关系是一对一，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
&强调：线性表是一个序列，元素之间有先来后到的顺序；如果元素的个数是0，称为空表；如果元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他元素都有且只有一个前驱和后继；线性表中的元素是有限的。
2.线性表的相关操作
&3.实际问题中涉及到的关于线性表的更复杂的操作，完全可以用这些基本操作组合来实现。比如求两个集合A和B的并集，则可以遍历B中的每个元素，判断当前元素是否在集合A中，如果在就忽略，如果不在，就把当前元素插入到集合A中。运用上面提到的几个操作就可以实现这个效果：ListLength(L)，GetElem(L,i,*e)，LocateElem(L,e)以及
ListInsert(*L,i,*e)即可。下面是参考实现的代码
&4.线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。顺序存储结构封装需要三个属性：
存储空间的起始位置
线性表的最大存储容量
线性表的当前长度
&注意，数组的长度是存放线性表的存储空间的总长度，一般初始化后不变，而线性表的当前长度是线性表中元素的个数，是会变化的。
&5.插入操作的实现思路
如果插入位置不合理，抛出异常
如果线性表长度大于等于数组长度，则抛出异常或者动态增加数组容量。
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
把要插入的元素填入到位置i处。
线性表的长度加1。
&6.删除操作的实现思路
如果删除位置不合理，抛出异常
取出要被删除的元素
从被删除的元素的位置开始向后遍历到最后一个元素的位置，分别将它们都向前移动一个位置。
线性表的长度减1。
&7.顺序存储结构插入操作和删除操作的时间复杂度
最好的情况：要操作的元素刚好在最后一个位置，因为不需要移动任何元素，所以此时的时间复杂度为O(1)。
最坏的情况：要操作的元素刚好在第一个位置，那就意味着要移动所有的元素向前或者向后，此时的时间复杂度为O(n)。
平均情况：取中间值O(（n-1）/2
)，按照计算原则，时间复杂度还是O(n)。
&8.结论：线性表的顺序存储结构，在存、读数据的时候，不管是哪个位置，时间复杂度都是O(1)，而在插入或者删除时，时间复杂度都是O(n)。这就说明，这种结构比较适合元素个数比较稳定，不经常插入和删除元素，更多的操作是存取元素的应用。
&9.线性表顺序存储结构的优缺点
优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空间。可以快速的存取表中任意位置的元素。
缺点：插入和删除经常需要移动大量的元素；当线性表的长度变化较大时，难以确定存储空间的容量；因为需要的总是大块连续的空间，所以容易造成存储空间的“碎片”。
&10.顺序存储结构中插入和删除要移动大量元素，如何解决这个问题？有一种思路是让每个元素之间都留下空位置。但是这种方法有三个问题，第一，是耗费更多的内存空间，第二，不好确定到底留多大的位置合适，第三，如果要同时插入比留出来的空位置多的元素，那么其他元素的移动将会变得更加复杂。
&产生大量元素移动的根本原因就是要求元素的位置相邻，那么不考虑元素位置的相邻，哪里有空位就放在哪里，这样是否可行呢？
&11.线性表的链式存储结构。
&这种结构的特点就是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是内存中未被占用的任意位置。顺序存储结构中，每个数据元素只需要存储一个位置就够了，而链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的地址(一个指针)。
&存数据的称为数据域，存指针的称为指针域，这两部分信息组成的数据元素称为存储映像，或者结点(NODE)。n个结点链接成一个链表，即为线性表的链式存储结构。因为此链表中的每个结点中只包含一个指针域，所以叫做单链表。
&链表中的第一个结点的存储位置叫做头指针，最后一个结点的指针指向null。
&12.头结点与头指针
头指针是指向链表第一个结点的指针，如果链表有头结点的话，那就是指向头结点的指针。头指针具有标识作用，所以常用头指针冠以链表的名字(指针变量的名字)。无论链表是否为空，头指针均不为空，头指针是链表的必要元素。
头结点是为了操作的方便和统一而设立的，放在第一个元素的结点之前，它的数据域一般不存储任何信息(也可以用来存放链表的长度)。有了头结点，对在第一个元素结点之前插入结点和删除第一个元素结点的操作，就与操作普通结点统一了，头结点不是链表的必要元素。
&13.单链表的读取
我们不知道单链表的第i个元素到底在哪里，所以必须从第一个结点开始一个挨着一个找。获取链表第i个数据的操作思路：
声明一个结点p指向链表的第一个结点，初始化j表示现在指向哪个结点，从1开始
如果已经到了链表末尾，p还是空，则说明第i个元素不存在。如果查找成功，则返回结点p的数据。
&这个算法的核心思想叫做“工作指针后移”，这也是很多算法的常用技术。它的时间复杂度取决于i的位置，当i等于1时，则不需要遍历，O(1)，当i等于n时则遍历n-1次才可以，这是最坏的情况，时间复杂度为O(n)。
&由于单链表的结构中没有定义表的长度，所以就不方便使用for来控制循环。
&14.单链表的插入，下面是单链表第i个数据插入结点的算法思路
声明一个结点p指向链表的头结点，初始化j从1开始。
当j&1的时候，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
若到链表末尾p为空，则说明第i个元素不存在，如果p不为空，则查找成功，在系统中生成一个空节点S。
将要插入的数据e赋值给s-&data。
先将s-&next =
p-&next，然后p-&next =
s，注意这两句的顺序不能颠倒。如果颠倒的话，p的指针先改变了，p是指向s了，但是s又会指向自己，相当于s-&next
= s，成为死循环了，这是不行的。
上面的所有步骤都完成之后，返回成功。
&15.单链表的删除操作
要实现结点的删除操作，其实就是把它的前继结点的指针绕过它，直接指向它的后继结点。也就是p-&next
= p-&next-&next，
也可以表示为q =
p-&next，p-&next = q-&next
&16.单链表第i个结点删除算法的思路
声明结点p指向链表的第一个结点，初始化j=1
当j&1的时候，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
若到链表末尾p为空，则说明第i个元素不存在，如果p不为空，则查找成功，将要删除结点p-&next赋值给q，然后p-&next
= q-&next。
将q结点中的数据赋值给e，作为返回，最后释放q结点。
&17.单链表插入和删除操作的时间复杂度。
无论是单链表插入算法还是删除算法，它们都是由两部分组成，第一部分是遍历查找第i个元素，第二部分是实现插入和删除元素。从整个算法来说，它们的时间复杂度都是
O(n)。也就是说，如果我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，相对于顺序存储结构是没有太大优势的。
&但是如果，我们希望从第i个位置开始，连续插入十个元素，对于顺序存储结构，意味着每一次插入都需要移动(n-i)个位置，所以每次都是O(n)。而对于单链表来说，我们只需要在第一次插入时找到第i个位置的指针，此时为O(n)，接下来只是简单的通过赋值移动指针而已，时间复杂度都是O(1)。
&显然，对于插入和删除数据越频繁的操作，单链表的效率优势就会越明显。
&18.单链表整表创建
声明一个结点p和计数变量i
初始化一个空链表L
让L的头结点的指针指向null，即建立一个带头结点的单链表
循环实现后继结点的赋值和插入。
&19.使用从前插入的方法建立单链表
先让新结点的next指向头结点之后，然后让表头的next指向新结点。
&20.尾插法建立单链表
&21.单链表的整表删除
&1&声明结点p和q
&2&将第一个结点赋值给p，下一个结点赋值给q
&3&释放p，将q赋值给p，循环执行。
要注意，这段代码中的q是不可或缺的，如果没有q，一旦释放了p，那就丢失了下一个结点的信息，这显然是不行的。
&22.总结，线性表的顺序存储结构和单链表各有其优缺点，不能简单的说哪个好，哪个不好，需要根据实际情况来综合平衡采用哪种数据结构更能满足需求。
&23.静态链表。用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。最后一个元素的游标指向第一个有数据的下标地址，
第一个元素的游标指向第一个没有数据的下标地址，除此之外，每一个游标都是指向它下个元素的下标。我们对数组的第一个和最后一个元素做特殊处理，它们的data不存放数据。我们通常把未使用的数组元素称为备用链表。
&24.静态链表的插入操作
&静态链表要解决的是，如何用静态模拟动态链表结构的存储空间分配，也就是需要的时候申请，
不需要的时候释放。解决的方法就是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表。每当要插入的时候，可以从备用链表上取得第一个结点作为待插入的新结点。
*************************************JS代码实现*************************************
&1.定义构造函数
&2.实现append( )方法，给列表的下一个位置增加一个新的元素，这个位置刚好等于变量listSize的值，当新元素就位后，变量listSize需要加1。
&3.实现find( )方法，通过对数组对象dataStore
进行迭代，查找给定的元素。如果找到，就返回该元素在列表中的位置，否则返回-1，这是在数组中找不到指定元素时返回的标准值。
& &4.实现remove(
)方法。首先，需要在列表中找到该元素，然后删除它，并且调整底层的数组对象以填补删除该元素后留下的空白。不过我们可以使用splice(
) 方法简化这一过程。
& &使用find( )方法返回的位置对数组dataStore
进行截取。数组改变后，将变量listSize
的值减1，以反映列表的最新长度。如果元素删除成功，该方法返回true，否则返回false。
& &5.length()
方法返回列表中元素的个数
& &6.toString()
方法，用来显示列表中的元素。严格说来，该方法返回的是一个数组，而不是一个字符串，但它的目的是为了显示列表的当前状态，因此返回一个数组就足够了。
& &7.insert(
)方法，用来把值插入到列表中某个元素之后。在实现中，insert( )方法用到了find( )方法，find()
方法会寻找传入的after参数在列表中的位置，找到该位置后，使用splice(
)方法将新元素插入该位置之后，然后将变量listSize
加1 并返回true，表明插入成功，否则返回false表示插入失败。
& &8.clear()方法用来清空列表中所有的元素。先用delete
操作符删除数组dataStore，接着在下一行创建一个空数组。最后一行将listSize 和pos的值设为0，表明这是一个新的空列表。
& &9.contains(
)方法用来判断给定值是否在列表中。
& &10.最后的一组方法允许用户在列表上自由移动，最后一个方法getElement()
返回列表的当前元素：
& &11.测试代码
& &12.使用迭代器访问列表，使用迭代器，可以不必关心数据的内部存储方式，以实现对列表的遍历，还有一些优点：
访问列表元素时不必关心底层的数据存储结构。
当为列表添加一个元素时，索引的值就不对了，此时只用更新列表，而不用更新迭代器
可以用不同类型的数据存储方式实现List
类，迭代器为访问列表里的元素提供了一种
统一的方式。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。以下试题来自：
填空题函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。 int GetElem(LinkList L,int i,Elemtype *e){
LinkList p；int j；p=L->j=1;
while(p&&ji)
return ERROR;*e=
(2)return OK;}
(1)p=p->next
(2)p->data
为您推荐的考试题库
您可能感兴趣的试卷
你可能感兴趣的试题
1.判断题 错2.判断题 错3.判断题 错4.判断题 对5.判断题 错}